#include <stdio.h>
#include <stdlib.h>

#define IN "kfib.in"
#define OUT "kfib.out"
#define MOD 666013

long long result[2][2], z[2][2];

void multiplication (long long a[2][2], long long b[2][2]){
    int i, j, c[2][2];

    c[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD;
    c[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD;
    c[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD;
    c[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD;

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

void power (int k){
    while(k){
        if (k % 2)
            multiplication (result, z);
        multiplication (z, z);
        k /= 2;
    }
}

int main()
{
    freopen (IN, "r", stdin);
    freopen (OUT, "w", stdout);

    int k;
    scanf ("%d", &k);

    result[1][1] = result[0][0] = 1;
    z[1][1] = z[0][1] = z[1][0] = 1;

    power (k);
    printf ("%d\n", result[0][1]);

    fclose (stdin);
    fclose (stdout);
    return 0;
}