#include <fstream>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

void produs(unsigned long long int a[][2],unsigned long long int b[][2]);

unsigned int fibonnaci_it(int index)
{
    unsigned long long int a[2][2],rezultat[2][2];
    rezultat[0][0]=rezultat[1][1]=1;
    rezultat[0][1]=rezultat[1][0]=0;
    a[0][0]=a[1][0]=a[0][1]=1;
    a[1][1]=0;
    while(index)
    {
        if(index%2==1)
           {
            produs(rezultat,a);
            index--;
           }
        produs(a,a);
        index/=2;
    }
 return rezultat[0][1];
}

int main()
{
    int n;
    fin>>n;
    fout<<fibonnaci_it(n)<<'\n';
    return 0;
}

void produs(unsigned long long int a[][2], unsigned long long int b[][2])
{
    unsigned long long int rez[2][2],i,j;
    rez[0][0]=((a[0][0]*b[0][0])%666013+(a[0][1]*b[1][0])%666013)%666013;
    rez[0][1]=((a[0][0]*b[0][1])%666013+(a[0][1]*b[1][1])%666013)%666013;
    rez[1][0]=((a[1][0]*b[0][0])%666013+(a[1][1]*b[1][0])%666013)%666013;
    rez[1][1]=((a[1][0]*b[0][1])%666013+(a[1][1]*b[1][1])%666013)%666013;
    for(i=0;i<=1;i++)
        for(j=0;j<=1;j++)
            a[i][j]=rez[i][j];
}