#include <bits/stdc++.h>

using namespace std;
const int MOD = 666013;

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

long long N;

struct mat {
    long long M[2][2];
};

mat A = {1, 0, 0, 1};
mat B = {1, 1, 1, 0};

mat MUL(mat a, mat b){
    mat mul;
    for(int i=0; i<2; i++){
        for(int j=0; j<2; j++){
            mul.M[i][j] = (a.M[i][0] * b.M[0][j] + a.M[i][1] * b.M[1][j]) % MOD;
        }
    }
    return mul;
}

mat pow(mat Mx, long long n){
    if(n == 0)
        return A;
    if(n % 2 == 0)
        return pow(MUL(Mx, Mx), n / 2);
    return MUL(Mx, pow(MUL(Mx, Mx), n / 2));
}

int main(){

    fin >> N;
    fout << pow(B, N).M[0][1];

    return 0;
}