#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;


#define modulo 666013

int a[2][2], m[2][2], aux[2][2], N;


void Inm(int a[][2], int b[][2], int c[][2])
{
     for(int i = 0; i < 2; i++)
             for(int j = 0; j < 2; j++) 
                     for(int k = 0; k < 2; k++)
                             c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % modulo;
}


int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    int i;
    scanf("%i", &N);
    N --;
    m[0][0] = a[0][0] = 0;
    m[1][1] = a[1][1] = 1;
    m[0][1] = a[0][1] = 1;
    m[1][0] = a[1][0] = 1;
    while(N)
    {
            if(N & 1)
            {
                 memset(aux, 0, sizeof(aux));
                 Inm(m, a, aux);
                 memcpy(m, aux, sizeof(aux));
                 N --;
            }
            memset(aux, 0, sizeof(aux));
            Inm(a, a, aux);
            memcpy(a, aux, sizeof(aux));
            N >>= 1;
    }
    printf("%i\n", m[0][1]);
    return 0;
}