#include <cstdio>
#include <cstring>

int main() {
    long long int N;
    long long int S[4][4], n, l; //Should be S[10^9][4], but we only need the last 3 lines!
    scanf("%lld", &N);

    const int cur = 0, p1=1, p2=2, p3=3;
    for(l=0;l<=3;l++) S[p1][l] = 1;

    for(n=1;n<=N;n++) {
        for(l=1;l<=3;l++) {
            S[cur][l] =  (
                        ((l>=1 && n>=1)?S[p1][1]:0) +
                        ((l>=2 && n>=2)?S[p2][2]:0) +
                        ((l>=3 && n>=3)?S[p3][3]:0)
                        ) % 100000;
        }

        if(n==N) continue;

        memcpy(S[p3], S[p2], 4*sizeof(long long int));
        memcpy(S[p2], S[p1], 4*sizeof(long long int));
        memcpy(S[p1], S[cur], 4*sizeof(long long int));
        memset(S[cur], 0, 4*sizeof(long long int));
    }

    printf("%lld\n", S[cur][3]);
    return 0;
}