#include <stdio.h>

#define MOD 666013

void multiply(long long A[2][2], long long B[2][2], long long 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;
}

void copy(long long A[2][2], long long B[2][2])
{
    A[0][0] = B[0][0];
    A[0][1] = B[0][1];
    A[1][0] = B[1][0];
    A[1][1] = B[1][1];
}

void power(long long base[2][2], long long exponent, long long result[2][2])
{
    long long temp[2][2];

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

    while (exponent > 0)
    {
        if (exponent % 2 == 1)
        {
            multiply(result, base, temp);
            copy(result, temp);
        }

        multiply(base, base, temp);
        copy(base, temp);

        exponent = exponent / 2;
    }
}

int main(void)
{
    FILE *fr = fopen("kfib.in", "r");

    if(!fr)
    {
      fprintf(stderr,"Failed to open read file");
      return -1;
    }

    FILE *fw = fopen("kfib.out", "w");

    if(!fw)
    {
      fprintf(stderr,"Failed to open write file");
      fclose(fr);
      return -1;
    }

    long long k;
    fscanf(fr, "%lld", &k);

    long long fib[2][2] = {
        {0, 1},
        {1, 1}
    };

    long long result[2][2];

    power(fib, k, result);

    fprintf(fw, "%lld", result[0][1]);

    fclose(fr);
    fclose(fw);

    return 0;
}