#include <bits/stdc++.h>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
const int mod = 666013;
int solve(int);
void mult(int a[3][3], int na, int ma, int b[3][3], int nb, int mb)
{
    int c[3][3] = {{0, 0, 0},
                   {0, 0, 0},
                   {0, 0, 0}};
    for (int i = 1; i <= na; i++)
        for (int j = 1; j <= mb; j++)
            for (int y = 1; y <= ma; y++)
                c[i][j] = (c[i][j] + 1ll * a[i][y] * b[y][j]) % mod;
    for (int i = 1; i <= na; i++)
        for (int j = 1; j <= mb; j++)
            a[i][j] = c[i][j];
}
int main()
{
    int n;
    f >> n;
    g << solve(n);
    return 0;
}
int solve(int x)
{
    int r[3][3] = {{0, 0, 0},
                   {0, 1, 0},
                   {0, 0, 1}};
    int a[3][3] = {{0, 0, 0},
                   {0, 0, 1},
                   {0, 1, 1}};
    for (x -= 2; x; x >>= 1)
    {
        if (x & 1)
            mult(r, 2, 2, a, 2, 2);
        mult(a, 2, 2, a, 2, 2);
    }
    a[1][1] = a[1][2] = 1;
    mult(a, 1, 2, r, 2, 2);
    return a[1][2];
}