#include <iostream>
#include <fstream>

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

int k;
int M[2][2], I[2][2];


void MultiplyMatrix(int A[2][2], int B[2][2]){
    int C[2][2];
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
            C[i][j] = ((1LL * A[i][0] * B[0][j])%666013 + (1LL * A[i][1] * B[j][1])%666013)%666013;
        }
    }
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++) A[i][j] = C[i][j]%666013;
}

int main()
{
    fin>>k;
    I[0][0] = I[1][1] = 1;
    M[0][1] = M[1][0] = M[1][1] = 1;
    for(int i = k-1; i!=0; i/=2){
        if(i&1){
            MultiplyMatrix(I, M);
        }
        MultiplyMatrix(M, M);
    }
    fout<<I[1][1];
    return 0;
}