#include <bits/stdc++.h>
using namespace std;
string np = "kfib";
ifstream f(np + ".in");
ofstream g(np + ".out");

// #define f cin
// #define g cout

int n;
const int mod = 666013;
void mult(int z[3][3], int size, int b[3][3])
{
    int aux[3][3] = {{0, 0, 0},
                     {0, 0, 0},
                     {0, 0, 0}};
    for (int i = 1; i <= size; i++)
        for (int j = 1; j <= 2; j++)
            for (int y = 1; y <= 2; y++)
                aux[i][j] = (aux[i][j] + 1ll * z[i][y] * b[y][j]) % mod;
    for (int i = 1; i <= size; i++)
        for (int j = 1; j <= 2; j++)
            z[i][j] = aux[i][j];
}
int rez(int x)
{
    int r[3][3] = {{0, 0, 0},
                   {0, 1, 0},
                   {0, 0, 1}};
    int z[3][3] = {{0, 0, 0},
                   {0, 0, 1},
                   {0, 1, 1}};
    for (x -= 2; x; x >>= 1)
    {
        if (x % 2 == 1)
            mult(r, 2, z);
        mult(z, 2, z);
    }
    z[1][1] = z[1][2] = 1;
    mult(z, 1, r);
    return z[1][2];
}
int main()
{
    f >> n;
    g << rez(n);

    return 0;
}