#include <cstdio>
using namespace std;
const long long MOD = 666013;
long long p[3][3], a[3][3];
void prod_mat(long long a[3][3], long long b[3][3], long long c[3][3])
{
    long long i, j, k;
    for(i = 1 ; i <= 2 ; i ++)
        for(j = 1 ; j <= 2 ; j ++)
        {
            c[i][j] = 0;
            for(k = 1 ; k <= 2 ; k ++)
                c[i][j] = (c[i][j] + (a[i][k] * b[k][j]) % MOD) % MOD;
        }
}
void cpy(long long a[3][3], long long b[3][3])
{
    int i, j;
    for(i = 1 ; i <= 2 ; i ++)
        for(j = 1 ; j <= 2 ; j ++)
            a[i][j] = b[i][j];
}
void fast_pow(long long k)
{
    long long b[3][3], i, j;
    for( ; k ; k = (k >> 1))
    {
        if(k & 1)
        {
            cpy(b, p);
            prod_mat(a, b, p);
        }
        prod_mat(a, a, b);
        cpy(a, b);
    }
}
int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    long long k;
    scanf("%lld", &k);
    p[1][1] = p[2][2] = a[2][1] = a[2][2] = a[1][2] = 1;
    fast_pow(k);
    printf("%lld\n", p[2][1]);
    return 0;
}