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

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

const int MOD = 666013;
int n;

void inmultire(long long sol[2][2], long long b[2][2])
{
    long long temp[2][2];
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            long long rez = 0;
            for (int k = 0; k < 2; k++)
            {
                rez = (rez + sol[i][k] * b[k][j]) % MOD;
            }
            temp[i][j] = rez;
        }
    }

    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            sol[i][j] = temp[i][j];
        }
    }
}

int main()
{
    in >> n;

    int p = n - 1;

    long long ans[2][2] = { {1, 0},
                            {0, 1} };

    long long mat[2][2] = { {0, 1},
                            {1, 1} };

    while(p > 0)
    {
        if (p & 1)
        {
            inmultire(ans, mat);
        }
        inmultire(mat, mat);
        p >>= 1;
    }

    long long M[2][2] = { {0, 1},
                          {0, 0} };

    inmultire(M, ans);

    out << ans[1][1];
    return 0;
}