# include <bits/stdc++.h>
using namespace std;
# define fi cin
# define fo cout
int t[2][2] = {1,1,1,0};
const int mod = 666013;
void matrix(int a[2][2],int b[2][2])
{
    int c[2][2];
    memset(c,0,sizeof(c));
    for (int k = 0;k < 2;++k)
        for (int i = 0;i < 2;++i)
            for (int j = 0;j < 2;++j)
               c[i][j] += (1LL * a[i][k] * b[k][j]) % mod,c[i][j] %= mod;
    for (int i = 0;i < 2;++i) for (int j = 0;j < 2;++j) a[i][j] = c[i][j];
}
int pow(int n)
{
    int a[2][2];
    for (int i = 0;i < 2;++i) for (int j = 0;j < 2;++j) a[i][j] = t[i][j];
    int ans[2][2];
    if (n&1)
    {
        --n;
        for (int i = 0;i < 2;++i)
            for (int j = 0;j < 2;++j) ans[i][j] = t[i][j];
    }
    else
    {
        while (!(n&1)) matrix(a,a),n >>= 1;
        for (int i = 0;i < 2;++i) for (int j = 0;j < 2;++j) ans[i][j] = a[i][j];
        --n;
    }
    while (n)
    {
        if (n&1) matrix(ans,a);
        n >>= 1;
        matrix(a,a);
    }
    return a[0][0];
}
int main(void)
{
     int t;
     ifstream fi("kfib.in");
     ofstream fo("kfib.out");
     int n;
     fi>>n;
     fo << pow(n-1) << '\n';
     return 0;
}