#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
int a[3][3], r[3][3], n;
void init()
{
    int i, j;
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
            a[i][j]=1;
    a[1][1]=0;
    r[1][1]=1; r[2][2]=1;
}
void inm(int a[][3],int b[][3])
{
    int i, j, k, aux[3][3];
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
            aux[i][j]=0;
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
            for(k=1; k<=2; k++)
                {
                    aux[i][j]+=(long long)a[i][k]*b[k][j]%MOD;
                    aux[i][j]%=MOD;
                }
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
            a[i][j]=aux[i][j];
}
int main()
{
    fin >> n;
    n--;
    if(n<0)
    {
        fout << 0;
        return 0;
    }
    init();
    while(n!=0)
    {
        if(n%2==1)
            inm(r, a);
        inm(a, a);
        n=n/2;
    }
    fout << r[2][2];
    return 0;
}