#include<iostream>
#include<fstream>
#define mod 666013
#define ll long long
using namespace std;
ifstream si("kfib.in");
ofstream so("kfib.out");

ll m[2][2]={{0,1},{1,1}};
ll x[2][2];
ll 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()
{

    int n;
    si>>n;
    putmat(n-1);
    so<<sol[1][1];
    so.close();

}