#include <bits/stdc++.h>
#define mod 666013
using namespace std;

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

int mt[3][3];
long long c[3][3];
long long b[3][3];
long long a[3][3];
int n;
int cont=0;
void inmultire(long long  x[3][3] , long long y[3][3] , long long reciver[3][3])
{
    long long a11 , a12 , a21 , a22;
    a11=x[1][1]*y[1][1]+x[1][2]*y[2][1];
    a12=x[1][1]*y[1][2]+x[1][2]*y[2][2];
    a21=x[2][1]*y[1][1]+x[2][2]*y[2][1];
    a22=x[2][1]*y[1][2]+x[2][2]*y[2][2];
    reciver[1][1]=a11%mod;
    reciver[1][2]=a12%mod;
    reciver[2][1]=a21%mod;
    reciver[2][2]=a22%mod;
}

void copiere(int x[3][3] , int y[3][3])
{
    x[1][1]=y[1][1];
    x[1][2]=y[1][2];
    x[2][1]=y[2][1];
    x[2][2]=y[2][2];
}
void matrice(int it)
{
    while(it>1)
    {
        if(it%2==1)
        {
               inmultire(b, c , c);
               --it;
        }
        else if(it%2==0)
        {
            inmultire(b,b,b);
            it=it/2;
        }


    }

}
int main()
{
    f>>n;
    a[1][1]=0;
    a[1][2]=1;

    c[1][1]=0;
    c[1][2]=1;
    c[2][1]=1;
    c[2][2]=1;


    b[1][1]=0;
    b[1][2]=1;
    b[2][1]=1;
    b[2][2]=1;


    matrice(n);
    inmultire(b , c , b);
    inmultire(b, a , b);
    g<<b[1][2]%mod;
    return 0;
}