#include<bits/stdc++.h>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

const long long MOD=666013;

long long n,matrice_de_start[5][5],a[5][5],ans[5][5],sol[5][5],d[5][5],c[5][5];

void inmultire_matrice(long long c[5][5],long long d[5][5])
{
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
    {
        long long s=0;
        for(int k=1;k<=2;k++)
            {
                s+=c[i][k]*d[k][j];
                s=s%MOD;
            }
        sol[i][j]=s;
    }
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
        c[i][j]=sol[i][j];
}


void lgput(int k)
{
    while(k)
    {
        if(k%2==1)
            inmultire_matrice(ans,a);
        inmultire_matrice(a,a);
        k=k/2;
    }
}

int main()
{
    fin>>n;
    if(n==0)
        cout<<0;
    else
    {
        matrice_de_start[1][2]=1;
        ans[1][1]=1;
        ans[2][2]=1;
        a[1][2]=1;
        a[2][1]=1;
        a[2][2]=1;
        lgput(n-1);
        inmultire_matrice(matrice_de_start,ans);
        fout<<matrice_de_start[1][2];
    }
    return 0;
}