#include <iostream>
#include <fstream>
#define MOD 666013
using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

int k;
unsigned long long a[2][2], b[2][2], c[2][2], r[2][2];

void init()
{
    a[0][0]=1;
    a[0][1]=1;
    a[1][0]=1;
    a[1][1]=0;
    b[0][0]=1;
    b[0][1]=1;
    b[1][0]=1;
    b[1][1]=0;
    r[0][0]=1;
    r[0][1]=1;
    r[1][0]=1;
    r[1][1]=0;
}

void mult(unsigned long long x[2][2], unsigned long long y[2][2], unsigned long long z[2][2])
{
    z[0][0]=((x[0][0]*y[0][0])%MOD+(x[0][1]*y[1][0])%MOD)%MOD;
    z[0][1]=((x[0][0]*y[0][1])%MOD+(x[0][1]*y[1][1])%MOD)%MOD;
    z[1][0]=((x[1][0]*y[0][0])%MOD+(x[1][1]*y[1][0])%MOD)%MOD;
    z[1][1]=((x[1][0]*y[0][1])%MOD+(x[1][1]*y[1][1])%MOD)%MOD;
}

void copiere(unsigned long long x[2][2], unsigned long long y[2][2])
{
    x[0][0]=y[0][0];
    x[0][1]=y[0][1];
    x[1][0]=y[1][0];
    x[1][1]=y[1][1];
}

void inmult()
{
    if(k==1 || k==2)
        g<<"1";
    else
    {
        int n=k-2;

        while(n)
        {
            if(n%2==0)
            {
                mult(a, a, c);
                copiere(a, c);
                n/=2;
            }
            else
            {
                mult(r, a, c);
                copiere(r, c);
                n--;
            }
        }

        g<<r[0][0];
    }
}

int main()
{
    f>>k;

    init();
    inmult();

    return 0;
}