#include <bits/stdc++.h>
#define mod 666013
#define m11 first.first
#define m12 first.second
#define m21 second.first
#define m22 second.second
#define matrix pair<pair<int,int>,pair<int,int>>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
matrix p={{1,0},{0,1}},a={{0,1},{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.m11;
    return 0;
}
matrix operator*(matrix X,matrix Y)
{
    int a11,a12,a21,a22;
    a11=(1LL*X.m11*Y.m11+1LL*X.m12*Y.m21)%mod;
    a12=(1LL*X.m11*Y.m12+1LL*X.m12*Y.m22)%mod;
    a21=(1LL*X.m21*Y.m11+1LL*X.m22*Y.m21)%mod;
    a22=(1LL*X.m21*Y.m12+1LL*X.m22*Y.m22)%mod;
    return {{a11,a12},{a21,a22}};
}