#include <iostream>
#include <fstream>
#define mod 666013
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
int k;
struct mat
{
    int x11,x12,x21,x22;
};
mat mult(mat x,mat y)
{
    mat t;
    t.x11=(1LL*x.x11*y.x11+1LL*x.x12*y.x21)%mod;
    t.x12=(1LL*x.x11*y.x12+1LL*x.x12*y.x22)%mod;
    t.x21=(1LL*x.x21*y.x11+1LL*x.x22*y.x21)%mod;
    t.x22=(1LL*x.x21*y.x12+1LL*x.x22*y.x22)%mod;
    return t;
}
mat exp(int b)
{
    mat a={0,1,1,1};
    mat rez={1,0,0,1};
    for(int i=1;i<(1<<30);i=i*2)
    {
        if(b&i)
        {
            rez=mult(rez,a);
        }
        a=mult(a,a);
    }
    return rez;
}
int main()
{
    in>>k;
    if(k<2)out<<k;
    if(k==2)out<<1;
    else
    {
        mat p=exp(k-2);
        int sum=(1LL*(p.x12+p.x22))%mod;
        out<<sum;
    }
    return 0;
}