#include <bits/stdc++.h>
#define mod 666013
#define m1 first
#define m2 second.first
#define m3 second.second
#define matrix pair<int,pair<int,int>>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
matrix p={1,{0,1}},a={0,{1,1}};
matrix operator*(matrix,matrix);
int k;
int main()
{
    f>>k;
    k++;
    for(;k;k>>=1)
    {
        if(k&1)
            p=p*a;
        a=a*a;
    }
    g<<p.m1;
    return 0;
}
matrix operator*(matrix X,matrix Y)
{
    return {(1LL*X.m1*Y.m1+1LL*X.m2*Y.m2)%mod,{(1LL*X.m1*Y.m2+1LL*X.m2*Y.m3)%mod,(1LL*X.m2*Y.m2+1LL*X.m3*Y.m3)%mod}};
}