#include <iostream>
#include <cstdio>
#define mod 666013

using namespace std;

long long n, putere;
long long a[2][2] = {{1,1},{1,0}}, b[2][2] = {{1,0},{0,1}}, c[2][2];

void copiere(long long a[][2] , long long b[][2])
{
    b[0][0] = a[0][0];
    b[0][1] = a[0][1];
    b[1][0] = a[1][0];
    b[1][1] = a[1][1];
}

void inmultire(long long a[][2], long long b[][2])
{
    c[0][0] = ((a[0][0] * b[0][0]) % mod + (a[0][1] * b[1][0]) % mod) % mod;
    c[0][1] = ((a[0][0] * b[0][1]) % mod + (a[0][1] * b[1][1]) % mod) % mod;
    c[1][0] = ((a[1][0] * b[0][0]) % mod + (a[1][1] * b[1][0]) % mod) % mod;
    c[1][1] = ((a[1][0] * b[0][1]) % mod + (a[1][1] * b[1][1]) % mod) % mod;

    copiere(c,b);
}

void prelucrare()
{
    while(putere != 1)
    {
        if(putere % 2 == 1)
        {
            putere--;

            inmultire(a,b);
        }

        inmultire(a,a);

        putere /= 2;
    }

    inmultire(a,b);

    printf("%lld",b[0][0]);
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);

    scanf("%lld",&n);

    putere = n - 1;

    prelucrare();

    return 0;
}