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

const int mod = 666013;

vector<vector<int>> mul(vector<vector<int>> a, vector<vector<int>> b)
{
    vector<vector<int>> c (2, vector<int>(2, 0));
    c[0][0] = ( 1LL * a[0][0] * b[0][0] + 1LL * a[0][1] * b[1][0] ) % mod;
    c[0][1] = ( 1LL * a[0][0] * b[0][1] + 1LL * a[0][1] * b[1][1] ) % mod;
    c[1][0] = ( 1LL * a[1][0] * b[0][0] + 1LL * a[1][1] * b[1][0] ) % mod;
    c[1][1] = ( 1LL * a[1][0] * b[0][1] + 1LL * a[1][1] * b[1][1] ) % mod;
    return c;
}

vector<vector<int>> exp(vector<vector<int>> a, int k)
{
    vector<vector<int>> rez(2, vector<int>(2, 0));
    rez[0] = {1, 0};
    rez[1] = {0, 1};
    while(k > 0)
    {
        if((k & 1))
        {
            rez = mul(a, rez);
        }
        a = mul(a, a);
        k = (k >> 1);
    }
    return rez;
}

signed main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    int k;
    cin >> k;
    vector<vector<int>> a(2, vector<int>(2, 1));
    a[0][0] = 0;
    a = exp(a, k);
    cout << a[1][0];
}