#include <stdio.h>
#include <string.h>
#define mod 666013
int mat[3][3];
int sol[3][3];
void inmultire(int a[3][3], int b[3][3])
{
    int c[3][3];
    memset(c, 0, sizeof(c));
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % mod;
    memcpy(a, c, sizeof(c));
}
void power(int n, int sol[3][3], int mat[3][3])
{
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            inmultire(sol, mat);
        }
        inmultire(mat, mat);
        n /= 2;
    }
}
int main()
{
    int n = 0;
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    scanf("%d", &n);
    mat[0][0] = 0;
    mat[0][1] = 1;
    mat[1][0] = 1;
    mat[1][1] = 1;
    sol[0][0] = 1;
    sol[0][1] = 0;
    sol[1][0] = 0;
    sol[1][1] = 1;
    power(n, sol, mat);
    printf("%d", sol[0][1]);
    return 0;
}