#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 666013;

long long a[3][3], b[3][3], c[3][3], rez[3][3], k;

void init()
{
    rez[1][1] = 1;
    rez[2][2] = 1;
    a[1][1] = 0;
    a[1][2] = 1;
    b[1][1] = 0;
    b[1][2] = b[2][1] = b[2][2] = 1;
}

void mult(long long a[3][3], long long b[3][3], long long c[3][3])
{
    c[1][1] = ((a[1][1] * b[1][1]) % MOD + (a[1][2] * b[2][1]) % MOD) % MOD;
    c[1][2] = ((a[1][1] * b[1][2]) % MOD + (a[1][2] * b[2][2]) % MOD) % MOD;
    c[2][1] = ((a[2][1] * b[1][1]) % MOD + (a[2][2] * b[2][1]) % MOD) % MOD;
    c[2][2] = ((a[2][1] * b[1][2]) % MOD + (a[2][2] * b[2][2]) % MOD) % MOD;
}

void sw(long long a[3][3], long long b[3][3])
{
    a[1][1] = b[1][1];
    a[1][2] = b[1][2];
    a[2][1] = b[2][1];
    a[2][2] = b[2][2];
}

void putere(long long k)
{
    while(k)
    {
        if(k & 1)
        {
            mult(rez, b, c);
            sw(rez, c);
            k--;
        }
        mult(b, b, c);
        sw(b, c);
        k >>= 1;
    }
}

int main()
{
    in>>k;
    if(k == 0)
        out<<0;
    else if(k == 1)
        out<<1;
    else
    {
        init();
        putere(k - 1);
        mult(a, rez, c);
        out<<c[1][2] % MOD;
    }
    return 0;
}