#include <fstream>
#define MOD 666013
#define ll long long
using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");
ll a[2][2]= {{0,1},{0,0}};  // matricea care are pe prima linie f(0) si f(1) si pe a doua linie 0 
ll c[2][2]= {{0,1},{1,1}};
ll sol[2][2]= {{1,0},{0,1}};  // matricea unitate
int n;

void mult(ll a[2][2],ll b[2][2])
{
    ll c[2][2];
    int i,j,k;
    for(i=0; i<=1; i++)
        for(j=0; j<=1; j++)
        {
            c[i][j]=0;
            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 put(ll sol[2][2],int n)
{
    while(n)
        if(n%2==1) { mult(sol,c); n--; }
        else { mult(c,c); n /= 2; }
}

int main()
{
    f>>n;
    put(sol,n);
    mult(a,sol);
    g<<a[0][0];
    return 0;
}