#include <iostream>
#include <fstream>

#define MOD 666013

using namespace std;

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

int k;
int 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(int x[2][2], int y[2][2], int 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;
    ///z[0][1]=x[0][0]*y[0][1]+x[0][1]*y[1][1];
    ///z[1][0]=x[1][0]*y[0][0]+x[1][1]*y[1][0];
    ///z[1][1]=x[1][0]*y[0][1]+x[1][1]*y[1][1];
}

void copiere(int x[2][2], int 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 inmultire()
{
    if(k==1 || k==2)
        fout<<"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--;
            }
        }
        fout<<r[0][0];
    }
}

int main()
{
    fin>>k;
    init();
    inmultire();
    return 0;
}