#include <iostream>
#include <fstream>

#define mod 666013

using namespace std;

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

int a[3][3], p[3];

void produs (int p[3][3],int a[3][3], int b[3][3])
{
    int aux[3][3];
    for (int i=1;i<=2;i++)
        for (int j=1;j<=2;j++)
        {
            aux[i][j]=0;
            for (int k=1;k<=2;k++)
                aux[i][j]+=1LL*a[i][k]*b[k][j]%mod;
            aux[i][j]%=mod;
        }
    for (int i=1;i<=2;i++)
        for (int j=1;j<=2;j++)
            p[i][j]=aux[i][j]%mod;
}


void produs2 (int p[3],int a[3],int b[3][3])
{
    int aux[3];
    aux[1]=aux[2]=0;
    aux[1]=(1LL*a[1]*b[1][1]%mod+1LL*b[1][2]*a[2]%mod)%mod;
    aux[2]=(1LL*b[2][1]*a[1]%mod+1LL*b[2][2]*a[2]%mod)%mod;
    p[1]=aux[1];
    p[2]=aux[2];
}


int main()
{
    int k;
    in>>k;

    a[1][1] = a[1][2] = a[2][1] = 1;
    p[1] = 1;
    while (k!=0)
    {
        if (k%2!=0)
        {
            produs2 (p,p,a);
        }
        produs (a,a,a);
        k/=2;
    }
    out<<p[2];
    return 0;
}