#include <bits/stdc++.h>
using namespace std;
long long n,i,a[5][5],sol[5][5],MOD=666013,co[5][5];
int main()
{
    ifstream f ("kfib.in");
    ofstream g ("kfib.out");
    f>>n;
    if(n==1||n==2)
    {
        g<<1;
        return 0;
    }
    --n;
    a[1][2]=a[2][1]=a[2][2]=1;
    sol[1][1]=sol[2][2]=1;
    for(i=n; i; i/=2)
    {
        if(i&1)
        {
            co[1][1]=co[1][2]=co[2][1]=co[2][2]=0;
            co[1][1]=(sol[1][1]*a[1][1]+sol[1][2]*a[2][1])%MOD;
            co[1][2]=(sol[1][1]*a[1][2]+sol[1][2]*a[2][2])%MOD;
            co[2][1]=(sol[2][1]*a[1][1]+sol[2][2]*a[2][1])%MOD;
            co[2][2]=(sol[2][1]*a[1][2]+sol[2][2]*a[2][2])%MOD;
            sol[1][1]=co[1][1];
            sol[1][2]=co[1][2];
            sol[2][1]=co[2][1];
            sol[2][2]=co[2][2];
        }
        co[1][1]=co[1][2]=co[2][1]=co[2][2]=0;
        co[1][1]=(a[1][1]*a[1][1]+a[1][2]*a[2][1])%MOD;
        co[1][2]=(a[1][1]*a[1][2]+a[1][2]*a[2][2])%MOD;
        co[2][1]=(a[2][1]*a[1][1]+a[2][2]*a[2][1])%MOD;
        co[2][2]=(a[2][1]*a[1][2]+a[2][2]*a[2][2])%MOD;
        a[1][1]=co[1][1];
        a[1][2]=co[1][2];
        a[2][1]=co[2][1];
        a[2][2]=co[2][2];
    }
    g<<(sol[1][1]+sol[1][2])%MOD<<'\n';
    return 0;
}