#include <bits/stdc++.h>
#define mod 666013

using namespace std;
int k, a[3][3], Sol;
void inmulteste(int a[3][3], int b[3][3])
{
    int i, j, rez[3][3] = {0}, k;
    for(i = 1; i <= 2; i++)
        for(j = 1; j <= 2; j++)
            for(k = 1; k <= 2; k++)
                rez[i][j] = (1ll * a[i][k] * b[k][j] + rez[i][j]) % mod;
    for(i = 1; i <= 2; i++)
        for(j = 1; j <= 2; j++)
            b[i][j] = rez[i][j];
}
void ExpLog()
{
    int sol[3][3] = {0};
    int i;
    sol[1][1] = sol[2][2] = 1;
    for(i = 1; i <= k; i<<=1)
    {
        if(i & k)
            inmulteste(a, sol);
        inmulteste(a, a);
    }
    Sol = sol[1][1];
}
int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    scanf("%d", &k);
    a[1][1] = a[1][2] = a[2][1] = 1;
    if(k == 0)
    {
        printf("0\n");
        return 0;
    }
    if(k == 1)
    {
        printf("1\n");
        return 0;
    }
    k--;
    ExpLog();
    printf("%d", Sol);
    return 0;
}