#include <bits/stdc++.h>
using namespace std;

const int MOD = 666013;

struct matrix {
    int mat[2][2];
    int rows, columns;
};

matrix f01, constMat;

matrix mult(matrix a, matrix b) {
    /// a.columns = b.rows
    matrix ans;
    ans.rows = a.rows;
    ans.columns = b.columns;
    for(int i = 0; i < ans.rows; i++)
        for(int j = 0; j < ans.columns; j++)
            ans.mat[i][j] = 0;
    for(int i = 0; i < ans.rows; i++)
        for(int j = 0; j < ans.columns; j++)
            for(int k = 0; k < a.columns; k++)
                ans.mat[i][j] = (ans.mat[i][j] + (long long) a.mat[i][k] * b.mat[k][j] % MOD) % MOD;
    return ans;
}

matrix logput(int n) {
    matrix ans;
    ans.rows = ans.columns = 2;
    ans.mat[0][0] = ans.mat[1][1] = 1;
    ans.mat[0][1] = ans.mat[1][0] = 0;
    while(n) {
        if(n % 2 == 1)
            ans = mult(ans, constMat);
        constMat = mult(constMat, constMat);
        n /= 2;
    }
    return ans;
}

int main() {
    int k;
    FILE *fin, *fout;
    fin = fopen("kfib.in", "r");
    fscanf(fin, "%d", &k);
    fclose(fin);
    f01.rows = 1;
    f01.columns = 2;
    f01.mat[0][0]= 0;
    f01.mat[0][1] = 1;
    constMat.rows = constMat.columns = 2;
    constMat.mat[0][0] = 0;
    constMat.mat[0][1] = constMat.mat[1][0] = constMat.mat[1][1] = 1;
    matrix ans;
    ans = logput(k);
    ans = mult(f01, ans);
    fout = fopen("kfib.out", "w");
    fprintf(fout, "%d", ans.mat[0][0]);
    fclose(fout);
    return 0;
}