#include <bits/stdc++.h>
#define mod 666013

using namespace std;

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

int p[3][3], ans[3][3], aux[3][3];

void mult(int ans[][3], int p[0][3], int aux[][3])
{
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            for(int k = 0; k < 2; ++k)
                aux[i][j] = (aux[i][j] + 1LL * ans[i][k] * p[k][j]) % mod;
}

void exp(int pwr)
{
    ans[0][0] = 1, ans[1][1] = 1;
    p[0][0] = 0, p[0][1] = 1, p[1][0] = 1, p[1][1] = 1;
    while(pwr) {
        if(pwr & 1) {
            memset(aux, 0, sizeof(aux));
            mult(ans, p, aux);
            memcpy(ans, aux, sizeof(aux));
        }
        memset(aux, 0, sizeof(aux));
        mult(p, p, aux);
        memcpy(p, aux, sizeof(aux));
        pwr >>= 1;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0);

    int n;
    fin >> n;
    exp(n - 1);
    if(ans[1][1] < 0) ans[1][1] += mod;
    fout << ans[1][1];
    return 0;
}