#include <fstream>

using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
#define mod 666013
long long c[3][3],a[3][3],sol[3][3],k;
void inmultire(long long a[3][3],long long sol[3][3])
{
    long long c[3][3];
    c[0][0]=((a[0][0]*sol[0][0])%mod+(a[0][1]*sol[1][0])%mod)%mod;
    c[0][1]=((a[0][0]*sol[0][1])%mod+(a[0][1]*sol[1][1])%mod)%mod;
    c[1][0]=((a[1][0]*sol[0][0])%mod+(a[1][1]*sol[1][0])%mod)%mod;
    c[1][1]=((a[1][0]*sol[0][1])%mod+(a[1][1]*sol[1][1])%mod)%mod;
    a[0][0]=c[0][0];
    a[0][1]=c[0][1];
    a[1][0]=c[1][0];
    a[1][1]=c[1][1];
}
void put(long long sol[3][3],long long n)
{
    while(n){
    if(n%2==1) inmultire(sol,c),n--;
    else inmultire(c,c),n/=2;}
}

int main()
{
    f>>k;
    sol[0][0]=sol[1][1]=1;
    a[0][1]=a[0][0]=1;
    c[0][1]=c[1][1]=c[1][0]=1;
    put(sol,k-1);
    inmultire(a,sol);
    g<<a[0][0];
    return 0;
}