#include <fstream>
#define prim 666013
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
void fib(int n);
long long int a[3][3],n;
int main()
{
    cin>>n;
    if(n==1) {cout<<1;return 0;}
    fib(n-1);
    cout<<(a[1][1]+a[1][2])%prim;
    //cout<<a[1][1]<<" "<<a[1][2]<<'\n'<<a[2][1]<<" "<<a[2][2];
}
void fib(int n)
{
    long long int x,y,z,t;
    if(n==1)
    {
        a[1][1]=0;
        a[1][2]=1;
        a[2][1]=1;
        a[2][2]=1;
    }
    else
    {
        fib(n/2);
            x=a[1][1];
            y=a[1][2];
            z=a[2][1];
            t=a[2][2];
            a[1][1]=((x*x)%prim+(y*z)%prim)%prim;
            a[2][2]=((t*t)%prim+(y*z)%prim)%prim;
            a[1][2]=((x*y)%prim+(t*y)%prim)%prim;
            a[2][1]=((z*x)%prim+(z*t)%prim)%prim;
            if(n%2==1)
            {
            x=a[1][1];
            y=a[1][2];
            z=a[2][1];
            t=a[2][2];
            a[1][1]=y;
            a[1][2]=(x+y)%prim;
            a[2][1]=t;
            a[2][2]=(z+t)%prim;
            }
    }
}