#include <fstream>
#define int long long
#define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int a[3][3], b[3][3], sol[3][3];
void inmultire (int a[3][3], int b[3][3])
{
    int val1=a[1][1]*b[1][1]+a[1][2]*b[2][1], val2=a[1][1]*b[1][2]+a[1][2]*b[2][2];
    int val3=a[2][1]*b[1][1]+a[2][2]*b[1][2], val4=a[2][1]*b[1][2]+a[2][2]*b[2][2];
    a[1][1]=val1%mod, a[1][2]=val2%mod, a[2][1]=val3%mod, a[2][2]=val4%mod;
}
void power (int k)
{
    while (k)
    {
        if (k%2) inmultire (sol, a);
        k/=2;
        inmultire (a, a);
    }
}
signed main ()
{
    int k;
    f >> k;
    if(!k)
    {
        g <<0;
        return 0;
    }
    a[1][1]=0, a[1][2]=1, a[2][1]=1, a[2][2]=1;
    b[1][1]=0, b[1][2]=1;
    sol[1][1]=sol[2][2]=1;
    power (k-1);
    g << (sol[2][1]+sol[2][2])%mod;
}