#include <bits/stdc++.h>

using namespace std;

ifstream F("kfib.in");
ofstream G("kfib.out");

int k;
const int MOD=666013;

struct matrix{
    int m[2][2];
    matrix(){
        memset(m, 0, sizeof(m));
    }
    matrix operator * (matrix b){
        matrix c = matrix();
        for(int i = 0; i < 2; ++ i)
            for(int j = 0; j < 2; ++ j)
                for(int k = 0; k < 2; ++ k)
                    c.m[i][j]=(c.m[i][j]+1LL*m[i][k]*b.m[k][j])%MOD;
        return c;
    }
} z, unit, ans;

matrix put(matrix a, int p){
    if(!p) return unit;
    matrix no1=put(a, p/2);
    no1=no1*no1;
    if(p%2) no1=no1*a;
    return no1;
}

int main()
{
    F >> k;
    unit.m[0][0]=unit.m[1][1]=1;
    z.m[0][0]=0;z.m[0][1]=z.m[1][1]=z.m[1][0]=1;
    ans=put(z, k);
    G << ans.m[0][1];
    return 0;
}