#include <iostream>
#include <cstdio>
#define Modulo 666013
using namespace std;
long long m[2][2]={{1,1},{1,0}},z[2][2]={{1,0},{0,1}},prod[2][2],fib[2]={0,1};
int n;

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_mat(long long a[][2], long long b[][2])
{
    prod[0][0]=((a[0][0]*b[0][0])%Modulo+(a[0][1]*b[1][0])%Modulo)%Modulo;
    prod[0][1]=((a[0][0]*b[0][1])%Modulo+(a[0][1]*b[1][1])%Modulo)%Modulo;
    prod[1][0]=((a[1][0]*b[0][0])%Modulo+(a[1][1]*b[1][0])%Modulo)%Modulo;
    prod[1][1]=((a[1][0]*b[0][1])%Modulo+(a[1][1]*b[1][1])%Modulo)%Modulo;
    copiere(prod,b);
}

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


int main()
{
    read();
    n = n-1;
    while(n != 1)
    {
        if(n % 2 == 1)
        {
            inmultire_mat(m,z);
            n --;
        }
        inmultire_mat(m,m);
        n/=2;

    }
    inmultire_mat(m,z);
    printf("%lld",z[0][0]);
    return 0;
}