#include <fstream>
#include<vector>
using namespace std;

#define ll long long
#define mod 666013

ifstream cin("kfib.in");
ofstream cout("kfib.out");

vector<vector<ll>> matrixProd(vector<vector<ll>> mx1, vector<vector<ll>> mx2) {
    int n1 = mx1.size();
    int m1 = mx1[0].size();
    int n2 = mx2.size();
    int m2 = mx2[0].size();
    vector<vector<ll>> res = vector<vector<ll>>(m1);

    for (int i = 0; i < n1; i++) {
        for (int y = 0; y < m2; y++) {
            ll sum = 0;
            for (int j = 0; j < m1; j++) {
                sum = (sum + (mx1[i][j] * mx2[j][y])%mod) % mod;
            }
            res[i].push_back(sum);
        }
    }

    return res;
}

vector<vector<ll>> power(vector<vector<ll>> mx, ll m) {
    auto res = vector<vector<ll>>(mx.size(), vector<ll>(mx[0].size(),0));
    ll len = mx.size();
    for (int i = 0; i < len; i++) {
        res[i][i] = 1;
    }

    while (m > 0) {
        if (m % 2) {
            res = matrixProd(res, mx);
            m--;
        }
        else {
            mx = matrixProd(mx, mx);
            m /= 2;
        }
    }
    return res;
}


ll solve(ll n) {
    vector<vector<ll>> res;
    res = { {0,1},{1,1} };
    res = power(res, n - 1);
    res = matrixProd(res, { {1},{1} });
    return *(*res.rbegin()).rbegin();
}

int main()
{
    int i = 0, j, n, nr;
    cin >> n;
    cout << solve(n-1);
    return 0;
}