#include<bits/stdc++.h>
const int modul=666013;
using namespace std;
void inmult(long long M1[2][2],long long M2[2][2],long long M3[2][2])
{
     int i,j,l;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
    {
        M3[i][j]=0;
        for(l=0;l<2;l++)
            M3[i][j]=(M3[i][j]+M1[i][l]*M2[l][j])%modul;
    }
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
           M1[i][j]=M3[i][j];
}
long long M1[2][2]={{1,0},{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 M1[1][1];
}
int main()
{
    int k;
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    f>>k;
    g<<putere(k);

}