#include<iostream>
#include<fstream>
#include<stdio.h>
#define mod 666013
using namespace std;
long long m[2][2]={{0,1},{1,1}};
long long x[2][2];
long long sol[2][2]={{1,0},{0,1}};
void putmat(int z)
{
    while(z)
    {
        if(z%2==1)
        {
            x[0][0]=(sol[0][0]*m[0][0])%mod+(sol[0][1]*m[1][0])%mod;
            x[0][1]=(sol[0][0]*m[0][1])%mod+(sol[0][1]*m[1][1])%mod;
            x[1][0]=(sol[1][0]*m[0][0])%mod+(sol[1][1]*m[1][0])%mod;
            x[1][1]=(sol[1][0]*m[0][1])%mod+(sol[1][1]*m[1][1])%mod;
            sol[0][0]=x[0][0]%mod;
            sol[1][0]=x[1][0]%mod;
            sol[0][1]=x[0][1]%mod;
            sol[1][1]=x[1][1]%mod;
        }
        z=z/2;
        x[0][0]=(m[0][0]*m[0][0])%mod+(m[0][1]*m[1][0])%mod;
        x[0][1]=(m[0][0]*m[0][1])%mod+(m[0][1]*m[1][1])%mod;
        x[1][0]=(m[1][0]*m[0][0])%mod+(m[1][1]*m[1][0])%mod;
        x[1][1]=(m[1][0]*m[0][1])%mod+(m[1][1]*m[1][1])%mod;
        m[0][0]=x[0][0]%mod;
        m[0][1]=x[0][1]%mod;
        m[1][0]=x[1][0]%mod;
        m[1][1]=x[1][1]%mod;
    }
}
int main()
{
    ifstream si;
    si.open("kfib.in");
    FILE* so=fopen("kfib.out","w");
    int n;
    si>>n;
    putmat(n-1);
    fprintf(so,"%lli\n",sol[1][1]);
}