#include <bits/stdc++.h>
#define ull unsigned long long

using namespace std;
const int d = 666013;

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

ull N;

ull C[2][2] = {0, 1, 1, 1}, D[2][2] = {0, 1, 1, 1};
ull A[2][2];

int matrix(){
    for(int i=0; i<2; i++){
        for(int j=0; j<2; j++){
            A[i][j] = (D[i][0]*C[0][j] + D[i][1]*C[1][j]) % d;
        }
    }
    for(int i=0; i<2; i++){
        D[i][0] = A[i][0] % d;
        D[i][1] = A[i][1] % d;
    }
}

int main(){

    fin >> N;
    for(int i=0; i<N; i++)
        matrix();
    fout << A[1][1];

    return 0;
}