#include <iostream>
#include <cstdio>

#define mod 666013

using namespace std;

long long a[2][2]={0, 1, 1, 1}, rez[2][2]={0, 1, 1, 1}, k;

void Inmultire(long long b[2][2], long long c[2][2])
{
    long long x=((b[0][0]*c[0][0])%mod+(b[0][1]*c[1][0])%mod)%mod;
    long long y=((b[0][0]*c[0][1])%mod+(b[0][1]*c[1][1])%mod)%mod;
    long long z=((b[1][0]*c[0][0])%mod+(b[1][1]*c[1][0])%mod)%mod;
    long long q=((b[1][0]*c[0][1])%mod+(b[1][1]*c[1][1])%mod)%mod;
    rez[0][0]=x;
    rez[0][1]=y;
    rez[1][0]=z;
    rez[1][1]=q;
}

void Pow(int p)
{
    if(p==1)
        return;
    if(p%2==0)
    {
        Pow(p/2);
        Inmultire(rez, rez);
    }
    else{
        Pow(p-1);
        Inmultire(a, rez);
    }
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    scanf("%d\n", &k);
    Pow(k-1);
    cout<<rez[1][1]%mod;
    return 0;
}