#include <iostream>
#include <fstream>

typedef unsigned long long mat[2][2];
#define mod 666013

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

long long k;
mat a,A;

void inm (mat a, mat b, mat c)
{
    mat d;
    d[0][0]=((a[0][0]*b[0][0])%mod+(a[0][1]*b[1][0])%mod)%mod;
    d[0][1]=((a[0][0]*b[0][1])%mod+(a[0][1]*b[1][1])%mod)%mod;
    d[1][0]=((a[1][0]*b[0][0])%mod+(a[1][1]*b[1][0])%mod)%mod;
    d[1][1]=((a[1][0]*b[0][1])%mod+(a[1][1]*b[1][1])%mod)%mod;
    c[0][0]=d[0][0];
    c[0][1]=d[0][1];
    c[1][0]=d[1][0];
    c[1][1]=d[1][1];
}

void alan(mat a,int n,mat b)
{
    if(n==0)
        {
            b[0][0]=b[1][1]=1;
            b[0][1]=b[1][0]=0;
        }
    else
        {
            mat aux;
            alan(a,n/2,aux);
            inm(aux,aux,b);
            if(n%2==1)
                inm(b,a,b);
        }
}

int main()
{
    fin>>k;
    a[0][0]=0;
    a[0][1]=a[1][0]=a[1][1]=1;
    alan(a,k-1,A);
    fout<<A[1][1];

    return 0;
}