#include <bits/stdc++.h>

using namespace std;

long long n;

vector<long long> a11;
vector<long long> a12;
vector<long long> a21;
vector<long long> a22;
vector<long long> powers;

int log2(int k)
{
    int ans = 0;
    int x = 1;
    while (x < k) {
        ans++;
        x = x * 2;
    }

    return ans;
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n;

    int p = 666013;
    powers.push_back(1);
    for (long long i = 1; i <= 40; i++) {
        powers.push_back((2 * powers[i - 1]) % p);
    }

    a11.push_back(1);
    a12.push_back(1);
    a21.push_back(1);
    a22.push_back(0);
    for (long long i = 1; i <= 40; i++) {
        a11.push_back((a11[i - 1] * a11[i - 1] + a12[i - 1] * a21[i - 1]) % p);
        a12.push_back((a11[i - 1] * a12[i - 1] + a12[i - 1] * a22[i - 1]) % p);
        a21.push_back((a21[i - 1] * a11[i - 1] + a22[i - 1] * a21[i - 1]) % p);
        a22.push_back((a21[i - 1] * a12[i - 1] + a22[i - 1] * a22[i - 1]) % p);
    }

    long long ans = 0;

    ans = 0;
    long long ans11 = 1, ans12 = 0, ans21 = 0, ans22 = 1;
    long long ans11c, ans12c, ans21c, ans22c;

    while (n)
    {
        ans11c = (ans11 * a11[log2(n & -n)] + ans12 * a21[log2(n & -n)]) % p;
        ans12c = (ans11 * a12[log2(n & -n)] + ans12 * a22[log2(n & -n)]) % p;
        ans21c = (ans21 * a11[log2(n & -n)] + ans22 * a21[log2(n & -n)]) % p;
        ans22c = (ans21 * a12[log2(n & -n)] + ans22 * a22[log2(n & -n)]) % p;

        ans11 = ans11c;
        ans12 = ans12c;
        ans21 = ans21c;
        ans22 = ans22c;
        n -= (n & -n);
    }

    cout << ans21 << endl;

    return 0;
}