#include <iostream>
#include <fstream>

using namespace std;

int n;
long long M[3][3],A[3][3],aux[3][3];

int main()
{
    int i,j;
    FILE *f=fopen("kfib.in","r");
    FILE *g=fopen("kfib.out","w");
    fscanf(f,"%d",&n);
    M[1][2]=M[2][1]=M[2][2]=1;
    A[1][1]=A[2][2]=1;
    n--;
    while(n)
    {
        if(n>>1<<1!=n)
        {
            aux[1][1]=A[1][1]*M[1][1]+A[1][2]*M[2][1];
            aux[1][2]=A[1][1]*M[1][2]+A[1][2]*M[2][2];
            aux[2][1]=A[2][1]*M[1][1]+A[2][2]*M[2][1];
            aux[2][2]=A[2][1]*M[1][2]+A[2][2]*M[2][2];
            A[1][1]=aux[1][1]%666013;
            A[1][2]=aux[1][2]%666013;
            A[2][1]=aux[2][1]%666013;
            A[2][2]=aux[2][2]%666013;
        }
        aux[1][1]=M[1][1]*M[1][1]+M[1][2]*M[2][1];
        aux[1][2]=M[1][1]*M[1][2]+M[1][2]*M[2][2];
        aux[2][1]=M[2][1]*M[1][1]+M[2][2]*M[2][1];
        aux[2][2]=M[2][1]*M[1][2]+M[2][2]*M[2][2];
        M[1][1]=aux[1][1]%666013;
        M[1][2]=aux[1][2]%666013;
        M[2][1]=aux[2][1]%666013;
        M[2][2]=aux[2][2]%666013;
        n>>=1;
    }
    fprintf(g,"%d\n",A[2][2]);
    return 0;
}