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