#include <iostream>
#include <fstream>

using namespace std;

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

#define mod  666013

long long int A[2][2], P[2][2];

int n;

void inmultireexppar()
{
    long long int x1, x2, x3, x4;
    x1 = ((P[0][0] * P[0][0])%mod + (P[0][1] * P[1][0])%mod) % mod;
    x2 = ((P[0][0] * P[0][1])%mod + (P[0][1] * P[1][1])%mod) % mod;
    x3 = ((P[1][0] * P[0][0])%mod + (P[1][1] * P[1][0]) % mod) % mod;
    x4 = ((P[1][0] * P[0][1])%mod + (P[1][1] * P[1][1])%mod)%mod;
    P[0][0] = x1;
    P[0][1] = x2;
    P[1][0] = x3;
    P[1][1] = x4;
}

void inmultireexpimpar()
{
    long long int x1, x2, x3, x4;
    x1 = ((A[0][0] * P[0][0])%mod + (A[0][1] * P[1][0])%mod)%mod;
    x2 = ((A[0][0] * P[0][1])%mod + (A[0][1] * P[1][1])%mod)%mod;
    x3 = ((A[1][0] * P[0][0])%mod + (A[1][1] * P[1][0])%mod)%mod;
    x4 = ((A[1][0] * P[0][1])%mod + (A[1][1] * P[1][1])%mod)%mod;
    A[0][0] = x1;
    A[0][1] = x2;
    A[1][0] = x3;
    A[1][1] = x4;

}

int putere()
{
    while(n != 0)
    {
        if(n % 2 == 0)
            n/=2, inmultireexppar();
        else
            n--, inmultireexpimpar();
    }
    return A[1][0];
}

void setUp()
{
    fin >> n;
   A[1][1] = A[0][0] = 1;
   P[0][1] = P[1][0] = P[1][1] = 1;
}

int main()
{
    setUp();
    fout << putere();
    return 0;
}