//proc
//iepuri
//al k-lea termen
#include <stdio.h>
#define MOD 666013
using namespace std;
long long N,a[2][2],sol[2][2];
/*int put(int b)
{
    long long sol = 1;
    for(;b;b/=2)
    {
        if(b%2 == 1)
        {
            sol *= x;
            sol %= MOD;
        }
        x*=x;
        x %= MOD;
    }
    return sol;
}*/
void show(long long a[][2])
{
    long long i=0,j=0;
    for(;i<2;++i)
    {
        for(j=0;j<2;++j)
            printf("%d ",a[i][j]);
        printf("\n");
    }
    printf("\n");
}
void asign(long long where[][2], long long x[2][2])
{
    where[0][0] = x[0][0];
    where[0][1] = x[0][1];
    where[1][0] = x[1][0];
    where[1][1] = x[1][1];
}
void multiply(long long x[][2],long long y[][2],long long where[][2])
{
    long long c[2][2];
    c[0][0] = (x[0][0]*y[0][0])%MOD + (x[0][1]*y[1][0])%MOD;
    c[0][1] = (x[0][0]*y[0][1])%MOD + (x[0][1]*y[1][1])%MOD;
    c[1][0] = (x[1][0]*y[0][0])%MOD + (x[1][1]*y[1][0])%MOD;
    c[1][1] = (x[1][0]*y[0][1])%MOD + (x[1][1]*y[1][1])%MOD;
    asign(where,c);
}
void mod_matrix(long long x[][2])
{
    x[0][0] %= MOD;
    x[1][1] %= MOD;
    x[0][1] %= MOD;
    x[1][0] %= MOD;
}
void put(long long b)
{

    for(;b;b/=2)
    {
        if(b%2 == 1)
        {
            multiply(sol,a,sol);
            mod_matrix(sol);
        }
        multiply(a,a,a);
        mod_matrix(a);
    }
}
long long fib(long long n)
{
    if(n<=2)
        return 1;

    return fib(n-1) + fib(n-2);
}
int main()
{
    FILE*f = fopen("kfib.in","r");
    fscanf(f,"%lld",&N);
    fclose(f);

    a[0][0] = 0;
    a[0][1] = 1;
    a[1][0] = 1;
    a[1][1] = 1;
    sol[0][0] = 1;sol[1][0] = 0;sol[0][1] = 0;sol[1][1] = 1;
    put(N-1);
    //show(sol);
    FILE*g = fopen("kfib.out","w");
    fprintf(g,"%d ",sol[1][1]);
    fclose(g);
    return 0;
}