#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 666013;
int k;
int n,m;
int put;
int z[3][3], rezultat[3][3];

void inmultire_A_B(int a[3][3], int b[3][3], int rez[3][3])
{
    for (int i = 1;i <= n;++i)
         for (int j = 1;j <= m;++j)
              for (int k = 1;k <= n;++k)
                   rez[i][j] = (rez[i][j] + 1LL * a[i][k] * b[k][j]) % MOD;
}

int a[3][3], b[3][3], c[3][3];

void ridicare_la_putere(int baza[3][3], int exp)
{
    int rez[3][3];
    memset(rez, 0, sizeof rez);
    rez[1][1] = rez[2][2] = 1;
    while (exp > 0)
        if (exp % 2 == 0)
        {
            int aux[3][3];
            memset(aux, 0, sizeof aux);
            exp /= 2;
            inmultire_A_B(baza, baza, aux);
            for (int i = 1;i <= n;++i) for (int j = 1;j <= m;++j) baza[i][j] = aux[i][j] % MOD;
        }
        else
        {
            --exp;
            int aux[3][3];
            memset(aux, 0, sizeof aux);
            inmultire_A_B(rez, baza, aux);
            for (int i = 1;i <= n;++i) for (int j = 1;j <= m;++j) rez[i][j] = aux[i][j] % MOD;
        }
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= m;++j)
             rezultat[i][j] = rez[i][j] % MOD;
}

int main()
{
    in>>k;
    n = m = 2;
    z[1][1] = 0; z[1][2] = z[2][1] = z[2][2] = 1;
    ridicare_la_putere(z, k - 2);
    int mat[3][3];
    int sol[3][3];
    memset(sol, 0, sizeof sol);
    sol[1][2] = (rezultat[1][2] % MOD + rezultat[2][2] % MOD) % MOD;
    out<<sol[1][2] % MOD;
    return 0;
}