#include<iostream>
#include<fstream>
#define MOD 666013
using namespace std;
void inmultire(int n, int m, int p, int a[5][5], int b[5][5], int c[5][5])
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= p; j++)
        {
            c[i][j] = 0;
            for(int k = 1; k <= m; k++)
            {
                c[i][j] += (long long)a[i][k] * b[k][j]%MOD;
                c[i][j]=c[i][j]%MOD;
            }
        }
    }
}
void putere(int n, int m, int a[5][5], int e, int b[5][5])
{
    if(e == 1)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                b[i][j] = a[i][j];
            }
        }
    }
    else if(e % 2 == 1)
    {

        int c[5][5];
        putere(n, m, a, e - 1, c);
        inmultire(n, m, m, a, c, b);
    }
    else
    {
        int c[5][5];
        putere(n, m, a, e / 2, c);
        inmultire(n, m, m, c, c, b);
    }

}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    int k, fn,fm, f[5][5], z[5][5], zn,zm, r[5][5], g[5][5];
    cin >> k;
    k--;
    fn = 1;
    fm = 2;
    f[1][1] = 0;
    f[1][2] = 1;
    zn = 2;
    zm = 2;
    z[1][1] = 0;
    z[1][2] = 1;
    z[2][1] = 1;
    z[2][2] = 1;
    putere(zn, zm, z, k, r);
    inmultire(fn, fm, zm, f, r, g);
    cout << g[1][2];
}