#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 666013;
void prod(long long p[][2], long long a[][2], long long b[][2])
{
    long long aux[2][2];
    for (int i = 0; i < 2; i++)
    {
        for (int k = 0; k < 2; k++)
        {
            aux[i][k] = 0;
            for (int j = 0; j < 2; j++)
            {
                aux[i][k] = (aux[i][k] + (a[i][j] * b[j][k]) % MOD) % MOD;
            }
        }
    }
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            p[i][j] = aux[i][j];
}
void pwr(long long a[][2], long long p[][2], int n)
{
    long long aux[2][2] = {1, 1, 1, 1};
    while (n)
    {
        if (n & 1)
            prod(aux, aux, a);
        prod(a, a, a);
        n >>= 1;
    }
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            p[i][j] = aux[i][j];
}
long long a[2][2] = {1, 1, 1, 0};
int main()
{
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    int n;
    cin >> n;
    if (n == 0)
        cout << 0;
    else
    {
        pwr(a, a, n - 2);
        cout << a[0][0];
    }
}