#include <bits/stdc++.h>
#define MOD 666013

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

int a[3][3],b[3][3],n;

void Inmultire(int x[3][3],int y[3][3])
{
    int i,j,k;
    int mx[3][3];
    long long s;

    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
        {
            s=0;
            for(k=1;k<=2;k++)
                s+=(1LL*x[i][k]*y[k][j]);
            mx[i][j]=s%MOD;
        }

    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
            x[i][j]=mx[i][j];
}

void Lgput(int p)
{
    int unit[3][3];
    unit[1][1]=unit[2][2]=1;
    unit[1][2]=unit[2][1]=0;

    while(p)
    {
        if(p%2)Inmultire(unit,a);
        Inmultire(a,a);
        p/=2;
    }

    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            a[i][j]=unit[i][j];
}

int main()
{
    fin>>n;
    a[2][1]=a[2][2]=a[1][2]=1;
    b[1][2]=1;
    Lgput(n-1);
    Inmultire(b,a);
    fout<<b[1][2];
    return 0;
}