#include<bits/stdc++.h>
const int modul=666013;
using namespace std;
int A[3][3],Solutii[3][3];
void inmult(int M1[2][2],int M2[2][2],int M3[2][2])
{
    int i,j,l;
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
                for(l=0;l<2;l++)
                    M3[i][j]=(M3[i][j]+1LL*M1[i][l]*M2[l][j])%modul;

}
int M1[2][2]={{0,1},{0,1}},M2[2][2]={{0,1},{1,1}},M3[2][2];
int putere(int N)
{
    while(N>0)
    {
       if(N%2==1)
            inmult(M1,M2,M3);
       N=N/2;
       inmult(M1,M1,M3);
    }
    return M3[1][1];
}
int main()
{
    int k;
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    f>>k;
    g<<putere(k);

}