#include <bits/stdc++.h>
using namespace std;

const int n = 2;
const int m = 2;
const int nr = 666013;

void multMatrix(int x[n][m], int y[n][m], int result[n][m])
{
    long long temp[n][m];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            temp[i][j] = 0;
            for (int k = 0; k < m; k++)
            {
                temp[i][j] += ((long long)x[i][k] * (long long)y[k][j]) % nr;
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            result[i][j] = temp[i][j];
        }
    }
}

int lgcalc(int k, int a[n][m], int c[n][m])
{
    if (k == 0)
        return 0;
    if (k % 2 == 0)
    {
        multMatrix(a, a, a);
        return lgcalc(k / 2, a, c);
    }

    else
    {
        multMatrix(c, a, c);
        multMatrix(a, a, a);
        return lgcalc(k / 2, a, c);
    }
}

int main()
{
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    int z[2][2] = {{1, 1}, {1, 0}};
    int finalArray[2][2] = {{1, 0}, {0, 1}};
    int k;
    fin >> k;
    if (k == 0)
    {
        fout << 0;
    }
    else
    {
        lgcalc(k - 1, z, finalArray);

        fout << finalArray[0][0] % nr;
    }

    return 0;
}