#include <stdio.h>

#define MOD 666013

long long int I2[2][2];

void mult_mat(long long int A[2][2], long long int B[2][2], long long int C[2][2])
{
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            C[i][j] = 0;
            for (int k = 0; k < 2; k++)
            {
                C[i][j] += (A[i][k] * B[k][j]) % MOD;
            }
        }
    }
}

void exp_log(long long int M[2][2], unsigned int n, long long int result[2][2])
{
    if (n == 0)
    {
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                result[i][j] = I2[i][j];
            }
        }
        return;
    }

    long long int R[2][2];
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            R[i][j] = M[i][j];
        }
    }

    while (n > 0)
    {
        if (n % 2)
        {
            long long int temp[2][2];
            mult_mat(result, R, temp);
            for (int i = 0; i < 2; i++)
            {
                for (int j = 0; j < 2; j++)
                {
                    result[i][j] = temp[i][j];
                }
            }
        }

        long long int temp[2][2];
        mult_mat(R, R, temp);
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                R[i][j] = temp[i][j];
            }
        }

        n = n / 2;
    }
}

int main()
{
    long long int k[2][2];
    int n;

    FILE *f, *g;

    long long int Z[2][2];

    f = fopen("kfib.in", "r");
    g = fopen("kfib.out", "w");

    fscanf(f, "%d", &n);

    // I2
    I2[0][0] = 0;
    I2[0][1] = 1;
    I2[1][0] = 1;
    I2[1][1] = 1;

    // K
    k[0][0] = 1;
    k[0][1] = 0;
    k[1][0] = 0;
    k[1][1] = 1;

    exp_log(k, n - 1, Z);

    fprintf(g, "%lld", Z[1][1] % MOD);

    fclose(f);
    fclose(g);

    return 0;
}