#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

#define MOD 666013
using namespace std;

vector<vector<long long>> matmul(vector<vector<long long>>& A, vector<vector<long long>>& B)
{
    vector<vector<long long>> res(2, vector<long long>(2, 0));
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                res[i][j] += A[i][k] * B[k][j];
                res[i][j] %= MOD;
                }
            }
        }

    return res;
}

int main(void)
{
    std::ios::sync_with_stdio(false);
    ifstream in("kfib.in");
    ofstream out("kfib.out");
    long long k;

    in >> k;

    if (k < 1) {
        cout << k;
        return 0;
    }
    
    k -= 2;

    vector<vector<long long>> m = {{0,1},{1,1}};
    vector<vector<long long>> res = {{1,0},{0,1}};

    while (k > 0) {
        if (k & 1) {
            res = matmul(res, m);
            k--;
        }
        m = matmul(m, m);
        k >>= 1;
    }

    cout << ((res[0][1] % MOD) + (res[1][1] % MOD)) % MOD<< "\n";

    return 0;
}