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

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


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

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

            for(p = 0; 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];


    memcpy(sol, m1, sizeof(m1));

    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[0][0] = 0; z[0][1] = z[1][0] = z[1][1] = 1;

    m1[0][0] = 0; m1[0][1] = 1;

    exp(K - 1);

    printf("%d\n", sol[0][1]);

    fclose(stdin);
    fclose(stdout);

    return 0;
}