#include <iostream>
#define mod 666013
#define MAX_N 2
#include <fstream>

using namespace std;

struct matrix{int mat[MAX_N][MAX_N];};

ifstream f("kfib.in");
ofstream g("kfib.out");

matrix matMul(matrix a, matrix b)
{
matrix ans;
int i,j,k;
for(i=0;i<MAX_N;i++)
    for(j=0;j<MAX_N;j++)
    {
    for(ans.mat[i][j]=k=0;k<MAX_N;k++)
        ans.mat[i][j]=(ans.mat[i][j]+(a.mat[i][k]*b[k][j])%mod)%mod;
    }
    return ans;
}

matrix matPow (matrix base, int p)
{
    matrix ans;
    int i,j;
    for(i=0;i<MAX_N;i++)
        for(j=0;j<MAX_N;j++)
            ans.mat[i][j]=(i==j);
    while(p)
    {
        if(p%2==1) ans=matMul(ans,base);
        base=matMul(base,base);
        p>>=1;
    }
    return ans;
}
int main()
{
    matrix ans,base;
    int n;
    f>>n;
    base.mat[0][0]=1;
    base.mat[0][1]=1;
    base.mat[1][0]=1;
    base.mat[1][1]=0;
    ans=matPow[base,n];
    g<<ans.mat[0][1];
    return 0;
}