#include <cstdio>
#include <cstring>

#define MOD 666013

FILE *fin, *fout;
int k;
long long m[3][3];
long long f[3][2];

void inm()  {
    long long m1[3][3] = {0LL};
    for(int i = 1;i <= 2;i++)
        for(int j = 1;j <= 2;j++)
            for(int k = 1;k <= 2;k++)
                m1[i][j] += m[i][k] * m[k][j] % MOD, m1[i][j] %= MOD;
    memcpy(m, m1, sizeof m1);
}

void inm1()  {
    long long f1[3][2] = {0LL};
    for(int i = 1;i <= 2;i++)
        for(int j = 1;j <= 1;j++)
            for(int k = 1;k <= 2;k++)
               f1[i][j] += m[i][k] * f[k][j] % MOD, f1[i][j] %= MOD;
    memcpy(f, f1, sizeof f1);
}

int main()  {
    fin = fopen("kfib.in", "r");
    fout = fopen("kfib.out", "w");
    fscanf(fin, "%d", &k);
    m[1][1] = m[1][2] = m[2][1] = 1LL;
    if(k <= 1)
        fprintf(fout, "1");
    f[1][1] = f[2][1] = 1LL;
    k--;
    while(k)  {
        if(k & 1)  {
            inm1();
        }
        k >>= 1;
        inm();
    }
    fprintf(fout, "%lld", f[2][1] % MOD);
    fclose(fin);
    fclose(fout);
    return 0;
}