#include <fstream>
#define MOD 666013

using namespace std;

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

int n, i, j;

void multiply(long long A[2][2], long long B[2][2], long long C[2][2]){
        for(int i = 0; i <= 1; i ++)
            for(int j = 0; j <= 1; j ++){
                C[i][j] = 0;
                for(int k = 0; k <= 1; k ++){
                    C[i][j] += A[i][k] * B[k][j];
                    C[i][j] %= MOD;
                }
            }
}
int main()
{
    fin >> n;
    if(n <= 2){
        fout << 1;
        return 0;
    }
    n -= 2;
    long long A[2][2] = { {1, 1}, {1, 0} };
    long long r[2][2] = { {1, 0}, {0, 1} };
    long long B[2][2];
    while(n){
        if(n % 2 != 0){
            multiply(r, A, B);
            for(i = 0; i <= 1; i ++)
                for(j = 0; j <= 1; j ++)
                    r[i][j] = B[i][j];
        }
        multiply(A,A,B);
        for(i = 0; i <= 1; i ++)
                for(j = 0; j <= 1; j ++)
                    A[i][j] = B[i][j];
        n /= 2;
    }

    fout << (r[0][0] + r[0][1]) % MOD;

    return 0;
}