#include <iostream>
#include <fstream>
#define M 666013
#define ull unsigned long long

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
ull A[2][2]={{0,1},{0,0}},
    C[2][2]={{0,1},{1,1}},
    sol[2][2]={{1,0},{0,1}};

void inmultire(ull a[2][2],ull b[2][2]) // a*b cu rez in a
{
    ull c[2][2];
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            c[i][j]=0;
            for(int k=0;k<2;k++)c[i][j]=(c[i][j]+a[i][k]*b[k][j])%M;
        }
    }
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)a[i][j]=c[i][j];
}

void putere(ull sol[2][2],int k) // sol=C^k
{
    while(k)
    {
        if(k%2==1)inmultire(sol,C),k--;
        else inmultire(C,C),k/=2;
    }
}

int main()
{
    int N;
    fin>>N;
    putere(sol,N); // sol=C^n
    inmultire(A,sol);
    fout<<A[0][0];
}