#include <fstream>
#define MOD 666013
using namespace std;
ifstream fin ("kfib.in");
ofstream fout("kfib.out");
int n;
long long a1[3][3],a2[3][3],a3[3][3];
void produs(long long a1[3][3],long long a2[3][3],long long a3[3][3]);
void aux(long long a1[3][3],long long a2[3][3]);
void declarare();
int main()
{
    fin>>n;
    declarare();
    while(n)
    {
        if(n%2!=0)
        {
            produs(a3,a1,a2);
            aux(a3,a2);
        }
        n=n/2;
        produs(a1,a1,a2);
        aux(a1,a2);

    }
    fout<<(a3[1][1]+a3[1][2])%MOD;
    return 0;
}
void produs(long long a1[3][3],long long a2[3][3],long long a3[3][3])
{
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            a3[i][j]=0;
            for(int k=1;k<=2;k++)
            {
                a3[i][j]=a3[i][j]+a1[i][k]*a2[k][j];
                a3[i][j]=a3[i][j]%MOD;
            }
        }
    }
}
void aux(long long a1[3][3],long long a2[3][3])
{
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            a1[i][j]=a2[i][j];
}
void declarare()
{
    a1[1][1]=1;
    a1[1][2]=1;
    a1[2][1]=1;
    a1[2][2]=0;
    a3[1][1]=1;
    a3[1][2]=0;
    a3[2][1]=0;
    a3[2][2]=1;
    n=n-2;
}