#include <iostream>
#include<fstream>
using namespace std;
#define R 666013
int k,i,j,p;
struct mat
{
    long long a[2][2];
}x,c,y;
mat X(mat a,mat b)
{
    for(i=0;i<2;++i)
    {
        for(j=0;j<2;++j)
        {
            c.a[i][j]=0;
            for(k=0;k<2;++k)
            {
                c.a[i][j]+=(a.a[i][k]*b.a[k][j])%R;
            }
            c.a[i][j]=c.a[i][j]%R;
        }
    }
    return c;
}
mat X1(mat a)
{
    for(i=0;i<2;++i)
    {
        for(j=0;j<2;++j)
        {
            c.a[i][j]=0;
            for(k=0;k<2;++k)
            {
                c.a[i][j]+=(a.a[i][k]*a.a[k][j])%R;
            }
            c.a[i][j]=c.a[i][j]%R;
        }
    }
    return c;
}
mat P(mat x,int p)
{
    if(p<2)return x;
    if(p%2>0)return X(P(x,p-1),x);
    return X1(P(x,p/2));
}
int main()
{
    x.a[0][0]=0;x.a[0][1]=1;x.a[1][0]=1;x.a[1][1]=1;
    ifstream f("kfib.in");f>>p;
    f.close();
    y=P(x,p-1);
    //for(i=0;i<2;i++){for(j=0;j<2;j++)cout<<y.a[i][j]<<" ";cout<<'\n';}
    ofstream g("kfib.out");g<<y.a[1][1];
    return 0;
}