#include <iostream>
#include <fstream>

using namespace std;

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

const int mod = 666013;

int a[2][2] = {{0, 1}, {1, 1}};
int r[2][2] = {{1, 0}, {0, 1}};
int c[2][2], d[2][2];

void mult_mat(int a[2][2], int b[2][2], int r[2][2])
{
    for(int j = 0; j <= 1; j++)
        for(int k = 0; k <= 1; k++)
            c[j][k] = a[j][k];

    for(int j = 0; j <= 1; j++)
        for(int k = 0; k <= 1; k++)
            d[j][k] = b[j][k];

    r[0][0] = 1LL * ((1LL * c[0][0] * d[0][0]) % mod + (1LL * c[0][1] * d[1][0]) % mod) % mod;
    r[0][1] = 1LL * ((1LL * c[0][0] * d[0][1]) % mod + (1LL * c[0][1] * d[1][1]) % mod) % mod;
    r[1][0] = 1LL * ((1LL * c[1][0] * d[0][0]) % mod + (1LL * c[1][1] * d[1][0]) % mod) % mod;
    r[1][1] = 1LL * ((1LL * c[1][0] * d[0][1]) % mod + (1LL * c[1][1] * d[1][1]) % mod) % mod;
}

int k;

int main()
{
    fin >> k;

    while(k){
        if(k % 2 == 1)
            mult_mat(r,a,r);
        mult_mat(a,a,a);
        k /= 2;
    }

    fout << r[0][1];

    return 0;
}