#include <iostream>
#include <fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
const int mod=666013;
int p[2][2]= {{1,0},{0,1}};
int m[2][2]= {{1,1},{1,0}};

void inm( int x[][2], int y[][2])
{
    long long z[2][2];
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
        {
            z[i][j]=0;
            for(int k=0; k<2; k++)
                z[i][j]+=1LL*x[i][k]*y[k][j];
        }
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            x[i][j]=z[i][j]%mod;
}
int powmat(int k)
{
    while(k>0)
    {
        if(k%2==0)
        {
            inm(m,m);
            k/=2;
        }
        else
        {
            inm(p,m);
            k--;
        }
    }
    return p[0][0];
}
int main()
{
    int K;
    f>>K;
    if(K==0) g<<'0'<<'\n';
    else
        g<<powmat(K-1)<<'\n';
    return 0;
}