#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize ("O1")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree <long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update>
#define lsb(x)(x & (-x))

const long long mod = 666013;

long long inm[3][3], aux[3][3], ans[3][3];

void prod (long long m1[3][3], long long m2[3][3], long long rez[3][3], long long n, long long m, long long p)
{
    for (long long i = 1; i <= n; i++)
    {
        for (long long j = 1; j <= p; j++)
        {
            aux[i][j] = 0;
        }
    }
    for (long long i = 1; i <= n; i++)
    {
        for (long long j = 1; j <= m; j++)
        {
            for (long long k = 1; k <= p; k++)
            {
                aux[i][j] = (aux[i][j] + (m1[i][k] * m2[k][j]) % mod) % mod;
            }
        }
    }
    for (long long i = 1; i <= n; i++)
    {
        for (long long j = 1; j <= p; j++)
        {
            rez[i][j] = aux[i][j];
        }
    }
}

void lgput (long long x)
{
    for (long long i = 1; i <= 2; i++)
    {
        ans[i][i] = 1;
    }
    while (x > 0)
    {
        if (x % 2 == 1)
        {
            prod(ans, inm, ans, 2, 2, 2);
        }
        prod(inm, inm, inm, 2, 2, 2);
        x /= 2;
    }
    for (long long i = 1; i <= 2; i++)
    {
        for (long long j = 1; j <= 2; j++)
        {
            inm[i][j] = ans[i][j];
        }
    }
}

void solve ()
{
    long long n;
    cin >> n;
    inm[1][2] = 1;
    inm[2][1] = 1;
    inm[2][2] = 1;
    lgput(n - 2);
    ans[1][1] = 1;
    ans[1][2] = 1;
    prod(ans, inm, ans, 1, 2, 2);
    cout << ans[1][2];
    cout << '\n';
}

signed main ()
{
#ifdef LOCAL
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif // LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long tt;
    //cin >> tt;
    tt = 1;
    while (tt--)
    {
        solve();
    }
    return 0;
}