#include <iostream>
#include <fstream>
#define MOD 666013

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

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

void inmultire_mat(unsigned long long x[5][5], unsigned long long y[5][5], unsigned long long z[5][5])
{
    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[5][5], unsigned long long y[5][5])
{
    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 inmultire()
{
    if(k==1 || k==2)
        fout<<"1";
    else
    {
        int n=k-2;
        while(n)
        {
            if(n%2==0)
            {
                inmultire_mat(a, a, c);
                copiere(a, c);
                n/=2;
            }
            else
            {
                inmultire_mat(r, a, c);
                copiere(r, c);
                n--;
            }
        }
        fout<<r[0][0];
    }
}


void atribuiri()
{
    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;
}

int main()
{
    fin >> k;
    atribuiri();
    inmultire();

    return 0;
}