#include <fstream>
#define mod  666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int n;
long long sol[3][3]={{1,0},{0,1}},a[3][3]={{0,1},{0,0}},c[3][3]={{0,1},{1,1}};
void inmultire(long long A[3][3], long long B[3][3])
{
    long long C[3][3],i,j,k;
    for(i=0;i<=1;i++)
        for(j=0;j<=1;j++)
    {
       C[i][j]=0;
        for(k=0;k<2;k++) C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%mod)%mod;
    }
     for(i=0;i<=1;i++)
        for(j=0;j<=1;j++) A[i][j]=C[i][j];
}
void putere(long long sol[3][3],int k)
{
    while(k)
    {
        if(k%2==1)
        {
            inmultire(sol,c);
            k--;
        }
        else
        {
            inmultire(c,c);
            k=k/2;
        }
    }
}
int main()
{
    f>>n;
    putere(sol,n);
    inmultire(a,sol);
    g<<a[0][0];
    return 0;
}