#include <fstream>
#include <string.h>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

#define mod 666013

long long n, a[3][3], sol[3][3];

void inm1()
{
    long long i, j, k, r[3][3];
    memset(r,0,sizeof(r));
    for (i = 1;i <= 2;i++)
        for (j = 1;j <= 2;j++)
        {
            for (k = 1;k <= 2;k++)
                r[i][j] += ((a[i][k] % mod) * (a[k][j] % mod)) % mod;
            r[i][j] %= mod;
        }
    memcpy(a,r,sizeof(r));
}

void inm2()
{
    long long i, j, k, r[3][3];
    memset(r,0,sizeof(r));
    for (i = 1;i <= 2;i++)
        for (j = 1;j <= 2;j++)
        {
            for (k = 1;k <= 2;k++)
                r[i][j] += ((sol[i][k] % mod) * (a[k][j] % mod)) % mod;
            r[i][j] %= mod;
        }
    memcpy(sol,r,sizeof(r));
}

void expo(int k)
{
    unsigned int i;
    for (i = 0;(1<<i) <= k;i++)
    {
        if (((1<<i) & k) > 0)
            inm2();
        inm1();
    }
}

int main()
{
    int i, j;
    f>>n;
    if (n == 0) { g<<0; return 0;}
    a[1][1] = 0; a[1][2] = 1;
    a[2][1] = 1; a[2][2] = 1;
    memcpy(sol,a,sizeof(a));
    expo(n - 2);
    g<<sol[2][2];
}