#include <bits/stdc++.h>

using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

long long K;
long long rez[2][2];
long long base[2][2];
long long aux[2][2];
int init[2];
int fin[2];
const int MOD = 666013;
void fastMatrixExponentiaion(long long exponent)
{
    rez[0][1] = 0;
    rez[1][0] = 0;
    rez[1][1] = rez[0][0] = 1;

    base[0][0] = 0;
    base[0][1] = 1;
    base[1][1] = 1;
    base[1][0] = 1;
    while (exponent)
    {
        if (exponent & 1)
        {
            for (int i = 0; i < 2; i++)
            {
                for (int j = 0; j < 2; j++)
                {
                    for (int k = 0; k < 2; k++)
                    {
                        aux[i][j] = (aux[i][j] + rez[i][k] * base[k][j])%MOD;
                    }
                }
            }
            for (int i = 0; i < 2; i++)
            {
                for (int j = 0; j < 2; j++)
                {
                    rez[i][j] = aux[i][j];
                    aux[i][j] = 0;
                }
            }
        }
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                for (int k = 0; k < 2; k++)
                {
                    aux[i][j] = (aux[i][j] + base[i][k] * base[k][j])%MOD;
                }
            }
        }
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                base[i][j] = aux[i][j];
                aux[i][j] = 0;
            }
        }
        exponent = exponent >> 1;
    }
}
int main()
{
    f >> K;
    init[0] = 0;
    init[1] = 1;
    fastMatrixExponentiaion(K);
    fin[0] = init[0] * rez[0][0] + init[1] * rez[1][0];
    fin[1] = init[0] * rez[0][1] + init[1] * rez[1][1];
    g<<fin[0];

}