#include<bits/stdc++.h>
#define int long long
#define MOD 666013
using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

int n,a[3][3],ans[3][3],z[3][3];

void inm(int sol[3][3], int x[3][3])
{
    int i,j,l;
    for(i=1;i<=2;i++)
    {
        for(j=1;j<=2;j++)
        {
            for(l=1;l<=2;l++)
            {
                z[i][j]+=(sol[i][l]*x[l][j]);
            }
        }
    }
    for(i=1;i<=2;i++)
    {
        for(j=1;j<=2;j++)
        {
            sol[i][j]=z[i][j]%MOD;
            z[i][j]=0;
        }
    }
}

signed main()
{
    int put=1,p;
    f>>n;
    p=n-1;
    a[1][1]=0;
    a[1][2]=1;
    a[2][1]=1;
    a[2][2]=1;
    ans[1][1]=0;
    ans[1][2]=1;
    while(p)
    {
        if(p&put)
        {
            inm(ans,a);
            p-=put;
        }
        put<<=1;
        inm(a,a);
    }
    g<<ans[1][2];
    return 0;
}