#include <bits/stdc++.h>

using namespace std;

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

int vid[5][5], n;
int a[5][5], b[5][5];
void Copiere(int a[][5], int b[][5])
{
    int i, j;
    for(i = 1;i <= 2;i++)
        for(j = 1;j <= 2;j++)
            a[i][j] = b[i][j];
}

void Inmultire(int a[][5], int b[][5])
{
    int i, j, k;
    int c[5][5];
    Copiere(c, vid);
    for(i = 1;i <= 2;i++)
        for(j = 1;j <= 2;j++)
            for(k = 1;k <= 2;k++)
                c[i][j] = (c[i][j] + 1ll *a[i][k] * b[k][j]) % 666013;
    Copiere(a, c);
}

void LgPow(int a[][5], int n)
{
    int p[5][5];
    Copiere(p, vid);
    p[1][1] = p[2][2] = 1;
    while(n)
    {
        if(n % 2 == 1)
            Inmultire(p, a);
        Inmultire(a, a);
        n /= 2;
    }
    Copiere(a, p);
}
int main()
{
    int i, j;
    fin >> n;
    a[1][2] = a[2][2] = a[2][1] = 1;
    b[1][2] = 1;
    b[1][1] = 0;
    LgPow(a, n - 1);
    Inmultire(b, a);
    fout << b[1][2];
    return 0;
}