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

using namespace std;

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

long long C[5][5];
void inmultire(long long A[5][5],long long B[5][5],long long n,long long m,long long t)
{
    long long i,j,k;
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    {
        C[i][j]=0;
        for(k=1;k<=t;k++)
        C[i][j]=(long long)(C[i][j]+(long long)(A[i][k]*B[k][j])%mod)%mod;
    }

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        A[i][j]=C[i][j];
}

long long n,putere,rez[5][5],neutru[5][5],A[5][5];

int main()
{
    f>>n;

    neutru[1][1]=0;neutru[1][2]=1;
    neutru[2][1]=1;neutru[2][2]=1;

    rez[1][1]=1;rez[1][2]=0;
    rez[2][1]=0;rez[2][2]=1;

    A[1][1]=1;A[1][2]=1;

    putere=n-2;
    while(putere!=0)
    {
        if(putere%2==1)inmultire(rez,neutru,2,2,2),putere--;
        else inmultire(neutru,neutru,2,2,2),putere/=2;
    }

    inmultire(A,rez,1,2,2);
    g<<A[1][2]<<'\n';
    return 0;
}