#include <fstream>
#define MOD 666013

using namespace std;

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

long long mat[10][10],c[10][10],n;

void inmultire(long long a[][10], long long b[][10])
{
    long long c[5][5]={0};
    long long i,j,k;
    for(i=0; i<2; i++)
        for(j=0; j<2; j++)
            for(k=0; k<2; k++)
                c[i][j]=(c[i][j]+a[i][k]*b[k][j]%MOD)%MOD;

    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            a[i][j]=c[i][j];
}


int main()
{
    fin>>n;
    mat[0][0]=mat[1][1]=1;
    c[0][1]=c[1][0]=c[1][1]=1;
    while(n)
    {
        if(n%2!=0)
            inmultire(mat,c);
        inmultire(c,c);
        n/=2;
    }

    fout<<mat[0][1];
}