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

#define MOD 666013

int n;

int C[3][3], eye[3][3];
int sol[3][2];

void inmultire(int A[3][3], int B[3][3])
{
        int rez[3][3] = {0};

        for (int i = 1; i <= 2; ++i)
        {
                for (int j = 1; j <= 2; ++j)
                {
                        for (int k = 1; k <= 2; ++k)
                                rez[i][j] = (rez[i][j] + 1LL * A[i][k] * B[k][j]) % MOD;
                }
        }

        for (int i = 1; i <= 2; ++i)
        {
                for (int j = 1; j <= 2; ++j)
                        A[i][j] = rez[i][j];
        }
}

void solve(int putere)
{
        while (putere > 0)
        {
                if (putere % 2 == 1)
                        inmultire (eye, C);

                inmultire (C, C);
                putere /= 2;
        }
}

int main()
{
        freopen ("kfib.in", "r", stdin);
        freopen ("kfib.out", "w", stdout);
        scanf ("%d", &n);

        C[1][1] = 0; C[1][2] = 1;
        C[2][1] = 1; C[2][2] = 1;
        eye[1][1] = 1; eye[1][2] = 0;
        eye[2][1] = 0; eye[2][2] = 1;
        sol[1][1] = 0; sol[2][1] = 1;

        if (n == 0)
                printf ("%d", sol[1][1]);
        else if (n == 1)
                printf ("%d ", sol[2][1]);
        else
                solve (n - 1);

        printf ("%d", (1LL * eye[2][1] * sol[1][1] + 1LL * eye[2][2] * sol[2][1]) % MOD);

        return 0;
}