#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int mod =666013;
int k;
int a[2][2],sol[1][2];
void inmlutire1(int A[1][2],int B[2][2])
{
    int C[1][2];
    for(int j = 0; j <= 1; ++j)
    {
        C[0][j] = 0;
        for(int k = 0; k <= 1; ++k)
            C[0][j] = (C[0][j] + (1LL*A[0][k]*B[k][j]))%mod;
    }
    for(int j = 0; j <= 1; ++j)
        A[0][j] = C[0][j];
}
void inmultire(int A[2][2],int B[2][2])
{
    int C[2][2];
    for(int i = 0; i <= 1; ++i)
        for(int j = 0; j <= 1; ++j)
        {
            C[i][j] = 0;
            for(int k = 0; k <= 1; ++k)
                C[i][j] = (C[i][j] + (1LL*A[i][k]*B[k][j]))%mod;
        }
    for(int i = 0; i <= 1; ++i)
        for(int j = 0; j <= 1; ++j)
            A[i][j] = C[i][j];
}
int main()
{
    a[0][1] = a[1][0] = a[1][1] = 1;
    sol[0][1] = 1;
    fin >> k;
    while(k)
    {
        if(k % 2 == 1)
            inmlutire1(sol,a);
        inmultire(a,a);
        k = k / 2;
    }
    fout << sol[0][0];
    return 0;
}