#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("kfib.in");
ofstream fout("kfib.out");
int mat[3][3];
int x[3][3];
int n,k;
void inmultire(int a[3][3], int b[3][3])
{
    int aux[3][3];
    memset(aux,0,sizeof(aux));
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++)
                aux[i][j]=(aux[i][j]+a[k][j]*b[i][k])%666013;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            a[i][j]=aux[i][j];
}
int main()
{
    fin>>k;n=k;
    mat[1][1]=mat[2][2]=1;
    x[1][1]=x[1][2]=x[2][2]=1;
    while(n>=1)
    {
        if(n%2==0)
        {
            inmultire(mat,mat);
            n=n/2;
        }
        else
        {
            inmultire(mat,x);
            n--;
        }
    }
    return 0;
}