#include <iostream>
#include <fstream>
#include <cstring>
#define MOD 666013

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

int k;

struct mat
{   long long m[3][3];
}ans, A;

mat prod(mat A, mat B)
{   mat sol;
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++) sol.m[i][j] = 0;
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++) sol.m[i][j] = (sol.m[i][j] + A.m[i][k] * B.m[k][j]) % MOD;
    return sol;
}

void lgput(int n)
{   while(n)
        {   if(n % 2 == 0) A = prod(A, A), n /= 2;
            else ans = prod(ans, A), n--;
        }

}

int main()
{
    f >> k;
    if(!k) g << 0 << '\n';
    else if(k == 1) g << 1 << '\n';
    else
        {   ans.m[0][0] = 0;
            ans.m[0][1] = 1;
            A.m[0][1] = A.m[1][0] = A.m[1][1] = 1;
            lgput(k-1);
            g << ans.m[0][1] << '\n';
        }
    return 0;
}