#include <bits/stdc++.h>
#define Mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
typedef long long ll;
ll N,M[3][3],C[3][3],R[3][3];

void init()
{
    for(int a=1;a<=2;a++)
    for(int b=1;b<=2;b++)
    for(int c=1;c<=2;c++) C[a][b]=0;
}

int main()
{
    f>>N;
    M[1][1]=M[1][2]=M[2][1]=1; M[2][2]=0;
    for(int i=1;i<=2;i++)
    for(int j=1;j<=2;j++) C[i][j]=M[i][j];
    R[1][1]=R[2][2]=1;

    for(int i=0;(1<<i)<=N;i++)
    {
        init();
        if( (N & (1<<i) )>0 )
        {
            for(int a=1;a<=2;a++)
            for(int b=1;b<=2;b++)
            for(int c=1;c<=2;c++)
            C[a][b]=(C[a][b]+(R[a][c]*M[c][b])%Mod)%Mod;

            for(int a=1;a<=2;a++)
            for(int b=1;b<=2;b++) R[a][b]=C[a][b];
        }
        init();

        for(int a=1;a<=2;a++)
        for(int b=1;b<=2;b++)
        for(int c=1;c<=2;c++)
        C[a][b]=(C[a][b]+(M[a][c]*M[c][b])%Mod)%Mod;

        for(int a=1;a<=2;a++)
        for(int b=1;b<=2;b++) M[a][b]=C[a][b];

    }
    g<<R[2][1];

    return 0;
}