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

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

long long n;
long long start[3][3];
long long M[3][3];
void inmultire(long long ma1[3][3], long long ma2[3][3])
{
    int rez[3][3];
    rez[1][1] = ((ma1[1][1] * ma2[1][1]) % MOD + (ma1[1][2] * ma2[2][1]) % MOD) % MOD;
    rez[1][2] = ((ma1[1][1] * ma2[1][2]) % MOD + (ma1[1][2] * ma2[2][2]) % MOD) % MOD;
    rez[2][1] = ((ma1[2][1] * ma2[1][1]) % MOD + (ma1[2][2] * ma2[2][1]) % MOD) % MOD;
    rez[2][2] = ((ma1[2][1] * ma2[1][2]) % MOD + (ma1[2][2] * ma2[2][2]) % MOD) % MOD;
    for (int i = 1; i <= 2; i++)
    {
        for (int j = 1; j <= 2; j++)
        {
            ma1[i][j] = rez[i][j];
        }
    }
}
void putere(long long k)
{
    while(k)
    {
        if (k % 2 == 0)
        {
            k /= 2;
            inmultire(M, M);
        }
        else
        {
            k--;
            inmultire(start, M);
        }
    }
}
int main()
{
    fin >> n;
    start[1][1] = 0;
    start[1][2] = 1;
    M[1][1] = 0;
    M[1][2] = 1;
    M[2][1] = 1;
    M[2][2] = 1;
    putere(n);
    fout << start[1][1];
    return 0;
}