#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#define ll long long
//i'm never leaving this project

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

const int mod=666013;
ll n,i,j,k,baza[3][3],b[3][3],c[3][3],sol,p;

void inmultire(ll a[3][3], ll b[3][3],ll rez[3][3])
{
    rez[1][1]=(a[1][1]*b[1][1]+a[1][2]*b[2][1])%mod;
    rez[1][2]=(a[1][1]*b[1][2]+a[1][2]*b[2][2])%mod;
    rez[2][1]=(a[2][1]*b[1][1]+a[2][2]*b[2][1])%mod;
    rez[2][2]=(a[2][1]*b[1][2]+a[2][2]*b[2][2])%mod;
}

void copyy(ll a[3][3],ll b[3][3])
{
    a[1][1]=b[1][1]; a[1][2]=b[1][2]; a[2][1]=b[2][1]; a[2][2]=b[2][2];
}

ll lgput(ll baza[3][3], ll p)
{
    ll A[3][3],aux[3][3];
    A[1][1]=A[2][2]=1;
    A[1][2]=A[2][1]=0;
    int b=32;
    while(b>=0)
    {
        if(p&1LL<<b)
        {
            inmultire(A,A,aux);
            copyy(A,aux);
            inmultire(A,baza,aux);
            copyy(A,aux);
        }
        else
        {
            inmultire(A,A,aux);
            copyy(A,aux);
        }
        b--;
    }
    return (A[2][1]+A[1][1])%mod;
}

int main()
{
    baza[1][1]=0; baza[1][2]=baza[2][1]=baza[2][2]=1;
    f>>p;
    p--;
    g<<lgput(baza,p);
    return 0;
}