#include <stdio.h>

#define MOD 666013

int main() 
{
    FILE *fin = fopen("kfib.in", "r");
    FILE *fout = fopen("kfib.out", "w");
    if(!fin || !fout) 
    {
        printf("nu s-a putut deschide un fisier!\n");
        return 1;
    }

    int K;
    fscanf(fin, "%d", &K);

    if(K == 0) 
    {
        fprintf(fout, "0\n");
        return 0;
    }

    int res[2][2] = {{1, 0},{0, 1}}; 
    int fib[2][2] = {{0, 1},{1, 1}}; 

    K--; 

    while(K > 0) 
    {
        if(K % 2 == 1) 
        {
            // res = res * fib % MOD
            int t00 = (1LL * res[0][0] * fib[0][0] + 1LL * res[0][1] * fib[1][0]) % MOD;
            int t01 = (1LL * res[0][0] * fib[0][1] + 1LL * res[0][1] * fib[1][1]) % MOD;
            int t10 = (1LL * res[1][0] * fib[0][0] + 1LL * res[1][1] * fib[1][0]) % MOD;
            int t11 = (1LL * res[1][0] * fib[0][1] + 1LL * res[1][1] * fib[1][1]) % MOD;
            res[0][0] = t00; res[0][1] = t01;
            res[1][0] = t10; res[1][1] = t11;
        }
        // fib = fib * fib % MOD
        int t00 = (1LL * fib[0][0] * fib[0][0] + 1LL * fib[0][1] * fib[1][0]) % MOD;
        int t01 = (1LL * fib[0][0] * fib[0][1] + 1LL * fib[0][1] * fib[1][1]) % MOD;
        int t10 = (1LL * fib[1][0] * fib[0][0] + 1LL * fib[1][1] * fib[1][0]) % MOD;
        int t11 = (1LL * fib[1][0] * fib[0][1] + 1LL * fib[1][1] * fib[1][1]) % MOD;
        fib[0][0] = t00; fib[0][1] = t01;
        fib[1][0] = t10; fib[1][1] = t11;

        K = K / 2;
    }

    fprintf(fout, "%d\n", res[1][1]);
    return 0;
}