#include <bits/stdc++.h>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define MOD 666013
long long a[2][2]= {{0,1},{0,0}},fib[2][2]= {{1,0},{0,1}},c[2][2]= {{0,1},{1,1}},n;
void inmultire(long long a[2][2],long long b[2][2])
{
    long long c[2][2],i,j,k;
    c[0][0]=c[0][1]=c[1][0]=c[1][1]=0;
    for(i=0; i<=1; ++i)
    {
        for(j=0; j<=1; ++j)
        {
            for(k=0; k<=1; ++k)c[i][j]+=a[i][k]*b[k][j];
            c[i][j]=c[i][j]%MOD;
        }
    }
    for(i=0; i<=1; ++i)for(j=0; j<=1; ++j) a[i][j]=c[i][j];
}
void putere(long long fib[2][2],int k)
{
    while(k)
    {
        if(k%2==1)inmultire(fib,c),k--;
        else inmultire(c,c),k/=2;
    }
}
int main()
{
    fin>>n;
    putere(fib,n);
    inmultire(a,fib);
    fout<<a[0][0];
    return 0;
}