#include <bits/stdc++.h>
#define maxN 3
#define mod 666013
using namespace std;
FILE *fin = freopen("kfib.in", "r", stdin);
FILE *fout = freopen("kfib.out", "w", stdout);

int n, m, a[maxN][maxN], b[maxN][maxN];
void mul(int a[maxN][maxN], int b[maxN][maxN])
{
    int res[maxN][maxN], i, j, k;
    for (i = 0; i < maxN; ++ i)
        for (j = 0; j < maxN; ++ j)
        {
            res[i][j] = 0;
            for (k = 0; k < maxN; ++ k)
                res[i][j] = (res[i][j] + 1LL * a[i][k] * b[k][j]) % mod;
        }

    memcpy(a, res, sizeof(res));
}
void read()
{
    scanf("%d", &n);
}
void solve()
{
    int i, j;
    a[0][0] = a[0][1] = 1;
    b[1][1] = b[0][1] = b[1][0] = 1;
    -- n;
    while (n)
    {
        if (n & 1)
            mul(a, b);
        mul(b, b);
        n >>= 1;
    }
}
void write()
{
    printf("%d\n", a[0][0]);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}