#include <iostream>
#include <fstream>
#define MOD 666013
#define int long long
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int n;
int a[2][2] ={
    {0, 1},
    {0, 0}
};
int c[2][2] = {
    {0, 1},
    {1, 1}
};
int sol[2][2] = {
    {1, 0},
    {0, 1}
};
void inmultire(int a[2][2], int b[2][2])
{
    int c[2][2];
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
    {
        c[i][j] = 0;
        for (int k = 0; k < 2; ++k)
        {
            c[i][j] += a[i][k] * b[k][j];
            c[i][j] %= MOD;
        }
    }
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            a[i][j] = c[i][j];
}
void exp(int sol[2][2], int k)
{
    while (k)
    {
        if (k % 2 == 1) inmultire(sol,c), --k;
            else inmultire(c,c), k /= 2;
    }
}
signed main()
{
    fin >> n;
    exp(sol,n);
    inmultire(a,sol);
    fout << a[0][0];
    return 0;
}