#include <iostream>
#include <fstream>
using namespace std;
#define mod 666013
ifstream f("kfib.in");
ofstream g("kfib.out");

long long z[3][3];
long long k;
long long a[3][3], c[3][3];

void pow_matrice(long long a[3][3], long long c[3][3]){

    c[0][0]=(a[0][0]*z[0][0]%mod+a[0][1]*z[1][0]%mod)%mod;
    c[0][1]=(a[0][0]*z[0][1]%mod+a[0][1]*z[1][1]%mod)%mod;
    c[1][0]=(a[1][0]*z[0][0]%mod+a[1][1]*z[1][0]%mod)%mod;
    c[1][1]=(a[1][0]*z[0][1]%mod+a[1][1]*z[1][1]%mod)%mod;

    for (int i=0; i<2; i++)
        for (int j=0; j<2; j++)
            a[i][j]=c[i][j];
}

int main(){

    a[0][0]=z[0][0]=0;
    a[0][1]=z[0][1]=1;
    a[1][0]=z[1][0]=1;
    a[1][1]=z[1][1]=1;
    f >> k;

    for (int i=1; i<k-1; i++)
        pow_matrice(a, c);

    g << a[1][1];
}