#include <iostream>
#include <cstdio>

using namespace std;



struct mat
{
    long long a=1,b=1,c=1,d=0;
} N;

int mod = 666013;


mat produs(mat m1, mat m2)
{
    mat rez;
    rez.a = ((m1.a * m2.a)%mod + (m1.b * m2.c)%mod)%mod;
    rez.b = ((m1.a * m2.b)%mod + (m1.b * m2.d)%mod)%mod;
    rez.c = ((m1.c * m2.a)%mod + (m1.d * m2.c)%mod)%mod;
    rez.d = ((m1.c * m2.b)%mod + (m1.d * m2.d)%mod)%mod;
    return rez;
}

mat f(mat n, int p)
{
    if(p==2)
    {
        return produs(n,n);
    }
    else if(p==1)
    {
        return n;
    }
    else if(p%2==0)
    {
        mat x = f(n,p/2);
        return produs(x,x);
    }
    else if(p%2==1)
    {
        mat x = f(n,p/2);
        return produs(produs(x,x),n);
    }

}




int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int k;
    scanf("%d",&k);
    mat x = f(N,k-1);
    printf("%d",x.a);
    return 0;
}