#include <iostream>
#include <fstream>

using namespace std;
ifstream r("kfib.in");
ofstream w("kfib.out");
const int mod=666013;
long long a[2][2], b[2][2], aux[2][2];
void ini()
{
    a[0][1]=a[1][0]=a[1][1]=1;
    b[0][1]=b[1][0]=b[1][1]=1;
}
void put(int c)
{
    while(c!=0)
    {
        if(c%2==1)
        {
            for(int i=0; i<2; i++)
            {
                for(int j=0; j<2; j++)
                {
                    aux[i][j]=b[i][j];
                }
            }
            b[0][0]=a[0][0]*aux[0][0]%mod+a[0][1]*aux[1][0]%mod;
            b[0][1]=a[0][0]*aux[0][1]%mod+a[0][1]*aux[1][1]%mod;
            b[1][0]=a[1][0]*aux[0][0]%mod+a[1][1]*aux[1][0]%mod;
            b[1][1]=a[1][0]*aux[0][1]%mod+a[1][1]*aux[1][1]%mod;
        }
        c/=2;
        for(int i=0; i<2; i++)
        {
            for(int j=0; j<2; j++)
            {
                aux[i][j]=a[i][j];
            }
        }
        a[0][0]=aux[0][0]*aux[0][0]%mod+aux[0][1]*aux[1][0]%mod;
        a[0][1]=aux[0][0]*aux[0][1]%mod+aux[0][1]*aux[1][1]%mod;
        a[1][0]=aux[1][0]*aux[0][0]%mod+aux[1][1]*aux[1][0]%mod;
        a[1][1]=aux[1][0]*aux[0][1]%mod+aux[1][1]*aux[1][1]%mod;
    }
}
int main()
{
    int k;
    r>>k;
    ini();
    put(k);
    w<<b[0][0];
    return 0;
}