#include <iostream>
using namespace std;
#define MOD 666013

void inmultire(long long a[2][2], long long b[2][2])
{
    long long rezultat[2][2];
    rezultat[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD;
    rezultat[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD;
    rezultat[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD;
    rezultat[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD;

    a[0][0] = rezultat[0][0];
    a[0][1] = rezultat[0][1];
    a[1][0] = rezultat[1][0];
    a[1][1] = rezultat[1][1];
}

void putere(long long F[2][2], long long n)
{
    long long rezultat[2][2] = {{1,0},{0,1}};
    while(n > 0)
    {
         if(n % 2 == 1)
         {
             inmultire(rezultat, F);
         }
         inmultire(F, F);
         n /= 2;
    }
    F[0][0] = rezultat[0][0];
    F[0][1] = rezultat[0][1];
    F[1][0] = rezultat[1][0];
    F[1][1] = rezultat[1][1];
}

long long fibonacci(long long k)
{
    if(k == 0)
    {
        return 0;
    }
    long long F[][2] = {{1,1},{1,0}};
    putere(F, k);
    return F[0][1];
}

int main()
{
    long long k;
    cin >> k;
    cout << fibonacci(k) << endl;
    return 0;
}