#include <bits/stdc++.h>
#define MOD 666013
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

long long ans = 0, a[3][3], crt, sol[3][3];

void multiplysol()
{
    long long w = sol[0][0], x = sol[0][1], y = sol[1][0], z = sol[1][1];

    sol[0][0] = (w * a[0][0] + x * a[1][0]) % MOD;
    sol[0][1] = (w * a[0][1] + x * a[1][1]) % MOD;
    sol[1][0] = (y * a[0][0] + z * a[1][0]) % MOD;
    sol[1][1] = (y * a[0][1] + z * a[1][1]) % MOD;
}

void multiplya()
{
    long long w = a[0][0], x = a[0][1], y = a[1][0], z = a[1][1];

    a[0][0] = (w * w + x * y) % MOD;
    a[0][1] = (w * x + x * z) % MOD;
    a[1][0] = (y * w + z * y) % MOD;
    a[1][1] = (y * x + z * z) % MOD;
}

void ridica_log(long long ex)
{
    a[0][0] = 0;
    a[0][1] = 1;
    a[1][1] = 1;
    a[1][0] = 1;
    sol[0][0] = 1;
    sol[0][1] = 0;
    sol[1][0] = 0;
    sol[1][1] = 1;

    crt = 1;

    while(ex != 0)
    {
        if((ex & crt) == crt)
            {
                multiplysol();
                ex -= crt;
            }
        multiplya();
        crt *= 2;
    }

    ans = sol[1][1];
}

int main()
{
    long long n;

    fin >> n;

    ridica_log(n-1);

    fout << ans << '\n';

    return 0;
}