#include<iostream>
#include<fstream>
using namespace std;
long a[2][2]={0,1,1,1};
long rez[2][2]={1,0,0,1};
long c[2][2];
void inmultire(long a[2][2],long b[2][2],long c[2][2])
{
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            {
                for(int q=0;q<2;q++)
                c[i][j]=(c[i][j]%666013+a[i][q]%666013*b[q][j]%666013)%666013;
            }
}
void ridicare(long n)
{
    while(n)
    {
        if(n%2)
        {
            inmultire(a,rez,c);

            for(int i=0;i<2;i++)
                for(int j=0;j<2;j++)
                {
                    rez[i][j]=c[i][j];
                    c[i][j]=0;
                }
                n--;
        }

        inmultire(a,a,c);
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
            {
                a[i][j]=c[i][j];
                c[i][j]=0;
            }
    n=n/2;

    }
    ofstream g("kfib.out");
    g<<rez[1][0]%666013;
}
int main()
{
    ifstream f("kfib.in");
    long n;
    f>>n;
ridicare(n);
}