#include <bits/stdc++.h>
#define Mod 666013
#define f first
#define s second
#define ll long long
#define matrix pair <pair <ll,ll>,pair <ll,ll> >
#define mp make_pair
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
matrix A,B;
ll N;

matrix Product(matrix A,matrix B)///cu modulo
{
    matrix C;ll c1,c2,c3,c4;
    c1=(A.f.f*B.f.f+A.f.s*B.s.f)%Mod;
    c2=(A.f.f*B.f.s+A.f.s*B.s.s)%Mod;
    c3=(A.s.f*B.f.f+A.s.s*B.s.f)%Mod;
    c4=(A.s.f*B.f.s+A.s.s*B.s.s)%Mod;
    C=mp(mp(c1,c2),mp(c3,c4));
    return C;
}

matrix Pow(matrix A,ll exponent)
{
    if(exponent==1)return A;
    if(exponent%2==0)
    {
        matrix C=Pow(A,exponent/2);
        return Product(C,C);
    }
    return Product(A,Pow(A,exponent-1));
}

void Type(matrix A)
{
    g<<A.f.f<<" "<<A.f.s<<"\n"<<A.s.f<<" "<<A.s.s;
}
int main()
{
    f>>N;A=mp(mp(0,1),mp(1,1));
    ///g<<A[0][0]<<" "<<A[0][1]<<"\n"<<A[1][0]<<" "<<A[1][1]<<"\n";
    B=Pow(A,N);
    ///Type(B);
    g<<B.f.s;
    return 0;
}