#include<fstream>
#define mod 666013
using namespace std;
int n;

struct matrice
{
    long long a,b,c,d;
}A,M;

void add(matrice B)
{
    matrice C;
    C.a=((A.a*B.a)%mod + (A.b*B.c)%mod)%mod;
    C.b=((A.a*B.b)%mod + (A.b*B.d)%mod)%mod;
    C.c=((A.c*B.a)%mod + (A.d*B.c)%mod)%mod;
    C.d=((A.c*B.b)%mod + (A.d*B.d)%mod)%mod;
    A=C;
}

void kfib(int n)
{
    if(n>1)
    {
        kfib(n/2);
        add(A);
        if(n%2==1)add(M);
    }
}

ifstream fin("kfib.in");
ofstream fout("kfib.out");

int main()
{
    fin>>n;
    M.a=0; M.b=1; M.c=1; M.d=1;
    A=M;
    kfib(n);
    fout<<A.b;
    return 0;
}