#include <bits/stdc++.h>
#define mod 666013

using namespace std;

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

long long c[4][4],baza[4][4];

void inmultire(long long a[4][4], long long b[4][4])
{
    for(int i=1;i<=2;i++)
    for(int j=1;j<=2;j++)
    {
        c[i][j]=0;
        for(int k=1;k<=2;k++)
            c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mod)%mod;
    }

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


void putere(long long a[4][4], long long exp)
{
    baza[1][1]=1;baza[1][2]=0;
    baza[2][1]=0;baza[2][2]=1;

    while(exp!=0)
    {
        if(exp%2==0)inmultire(a,a),exp/=2;
        else inmultire(baza,a),exp--;
    }

    for(int i=1;i<=2;i++)
    for(int j=1;j<=2;j++)
        a[i][j]=baza[i][j];
}

long long n,a[4][4];
int main()
{
    f>>n;

    a[1][1]=0;a[1][2]=1;
    a[2][1]=1;a[2][2]=1;

    if(n==0){g<<0;return 0;}
    else if(n==1){g<<1;return 0;}

    putere(a,n-1);
    g<<a[2][2]%mod;

    return 0;
}