#include <bits/stdc++.h>
#define ll long long
#define MOD 666013
using namespace std;

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

int K;
int dp[2][2], mat[2][2], ans[2][2];

void prepare() {
    dp[0][1] = 1;
    mat[0][1] = mat[1][0] = mat[1][1] = 1;
}
void mult(int A[2][2], int B[2][2]) {
    int C[2][2];
    memset(C, 0, sizeof(C));
    for (int i = 0; i < 2; ++i)
    for (int j = 0; j < 2; ++j)
    for (int k = 0; k < 2; ++k)
        C[i][j] = (C[i][j] + 1ll * A[i][k] * B[k][j]) % MOD;
    memcpy(A, C, sizeof(C));
}
void lgpow(int p) {
   ans[0][0] = ans[1][1] = 1;
   while (p) {
      if (p % 2) mult(ans, mat);
      mult(mat, mat);
      p /= 2;
   }
    memcpy(mat, ans, sizeof(ans));
}
int main()
{
    fin >> K;
    if (K <= 1) {
        fout << K << '\n';
        return 0;
    }

    prepare();
    lgpow(K - 1);
    mult(dp, mat);
    fout << dp[0][1] << '\n';

    return 0;
}