#include <bits/stdc++.h>
#define NMAX 1000001
#define MOD 666013

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

int n, k, M[2][2], M1[2][2], Z[2][2], I[2][2];

void multMat(int N1[][2], int N2[][2], int N3[][2]) {
    int R[2][2];
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            R[i][j] = 0;
        }
    }
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            for(int k = 0; k < 2; k++) {
                R[i][j] = (R[i][j] + 1LL * N1[i][k] * N2[k][j]) % MOD;
            }
        }
    }
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            N3[i][j] = R[i][j];
        }
    }
}

void raisePower(int pow) {
    I[0][0] = 1;
    I[0][1] = 0;
    I[1][0] = 0;
    I[1][1] = 1;
    for(int i = 0; (1 << i) <= pow; i++) {
        if(pow & (1 << i)) {
            multMat(I, Z, I);
        }
        multMat(Z, Z, Z);
    }
    /*while(pow > 0) {
        if(pow % 2 == 1) {
            multMat(I, Z, I);
            pow--;
        }
        multMat(Z, Z, I);
        pow /= 2;
    }*/
}

int main()
{
    Z[0][1] = 1;
    Z[1][0] = 1;
    Z[1][1] = 1;
    M1[0][0] = 1;
    M1[0][1] = 1;
    fin >> k;

    raisePower(k - 1);
    multMat(M1, I, M);
    fout << M[0][0] << '\n';
    return 0;
}