#include <iostream>
#include <fstream>

#define mod 666013

using namespace std;

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

int k;
long long a[2][2], s[2];

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

void Search()
{
    long long aux;
    for(int i=1; i<k; ++i)
    {
        aux=(s[0]*a[0][0]+s[1]*a[0][1])%mod;
        s[1]=(s[0]*a[1][0]+s[1]*a[1][1])%mod;
        s[0]=aux;
    }
    g<<s[0];
}

int main()
{
    f>>k;
    init();
    Search();
    return 0;
}