#include <iostream>
#include <fstream>

using namespace std;

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

const int MOD = 666013;
long long int z[5][5],ans[5][5];

void make_prod(long long int s[5][5]){
    long long int cop[5][5],A[5][5];
    for(int i = 1; i <= 2; i++){
        for(int j = 1; j <= 2; j++){
            cop[i][j] = ans[i][j];
            A[i][j] = s[i][j];
        }
    }
    ans[1][1] = ((cop[1][1] * A[1][1]) % MOD + (cop[1][2] * A[2][1]) % MOD) % MOD;
    ans[1][2] = ((cop[1][1] * A[1][2]) % MOD + (cop[1][2] * A[2][2]) % MOD) % MOD;
    ans[2][1] = ((cop[2][1] * A[1][1]) % MOD + (cop[2][2] * A[2][1]) % MOD) % MOD;
    ans[2][2] = ((cop[2][1] * A[1][2]) % MOD + (cop[2][2] * A[2][2]) % MOD) % MOD;
}

void solve(int k){
    if(k <= 1){
        return;
    }
    solve(k / 2);
    make_prod(ans);
    if(k % 2 == 1){
        make_prod(z);
    }
}

int main()
{
    int n;
    fin >> n;
    z[1][2] = z[2][1] = z[2][2] = ans[1][2] = ans[2][1] = ans[2][2] = 1;
    solve(n - 1);
    if(n == 0){
        fout << 0;
    } else {
        fout << ans[2][2];
    }
    return 0;
}