#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
void ori(long long a[][5], long long b[][5])
{
    long long c[5][5],s;
    for(int i=0;i<=1;++i)
    {
        for(int j=0;j<=1;++j)
        {
            s=0;
            for(int k=0;k<=1;++k)
                s=(s+b[k][j]*a[i][k]%MOD)%MOD;
            c[i][j]=s;
        }
    }

    for(int i=0;i<=1;++i)
        for(int j=0;j<=1;++j)
            a[i][j]=c[i][j];
}

void pwr(int p, long long a[][5])
{
    if(p>1)
    {
        if(p%2==0)
        {
            ori(a,a);
            pwr(p/2, a);
        }
        else
        {
            long long c[5][5];
            for(int i=0;i<=1;++i)
                for(int j=0;j<=1;++j)
                    c[i][j]=a[i][j];

            ori(a,a);
            pwr(p/2,a);
            ori(a,c);
        }
    }
}

long long k, ans[5][5], fib[5][5];
int main()
{
    fin>>k;

    fib[0][1]=fib[1][1]=fib[1][0]=1;
    pwr(k-2,fib);

    ans[0][0]=ans[0][1]=1;
    if(k-2>0)
        ori(ans,fib);
    fout<<ans[0][1];

    return 0;
}