#include<stdio.h>
#include<cstring>
#define inf  666013
using namespace std;

int z[3][3], sol[3][3], K;


int inm(int a[3][3], int b[3][3], int c[3][3])
{
    int i, j, p;

    for(i = 1; i <= 2; i++)
        for(j = 1; j <= 2; j++)
        {
            c[i][j] = 0;

            for(p = 1; p <= 2; p++)
                c[i][j] = (c[i][j] + 1LL * a[i][p] * b[p][i]) % inf;

        }
}



void exp(int n)
{
    int i, aux[3][3];

    for(i = 0; (1<<i) <= n; i++)
    {
        if((1<<i) & n)
        {
            memset(aux, 0, sizeof(aux));
            inm(sol, z, aux);
            memcpy(sol, aux, sizeof(aux));
        }

        memset(aux, 0, sizeof(aux));
        inm(z, z, aux);
        memcpy(z, aux, sizeof(aux));
    }

}



int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);

    scanf("%d", &K);

    z[1][1] = 0; z[1][2] = z[2][1] = z[2][2] = 1;

    sol[1][1] = sol[2][2] = 1;

    exp(K - 1);

    printf("%d", sol[2][2]);

    fclose(stdin);
    fclose(stdout);

    return 0;
}