#include <bits/stdc++.h>

using namespace std;

const int mod = 666013;

int baza[3][3], z[3][3], c[3][3];

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

int main()
{
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    int k;
    fin >> k;
    k -= 2;
    baza[1][2] = baza[2][1] = baza[2][2] = z[1][2] = z[2][1] = z[2][2] = 1;
    while(k){
        if(k % 2 == 1)
            mult(z, baza);
        mult(baza, baza);
        k /= 2;
    }
    fout << z[2][2] % mod;
    return 0;
}