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

using namespace std;

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

void inmultire(long long A[10][10],long long B[10][10])
{
    long long i,j,k,c[10][10];
    for(i=1;i<=2;i++)
    {
        for(j=1;j<=2;j++)
        {
            c[i][j]=0;
            for(k=1;k<=2;k++)
              c[i][j]=(c[i][j]+(A[i][k]*B[k][j])%mod)%mod;
        }
    }

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

void putere(long long putere,long long A[10][10])
{
    long long i,j,sol[10][10];
    sol[1][1]=sol[2][2]=1;
    sol[1][2]=sol[2][1]=0;

    while(putere)
    {
        if(putere%2==0)
        {
            inmultire(A,A);
            putere/=2;
        }
        else
        {
            inmultire(sol,A);
            putere--;
        }
    }

    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
        A[i][j]=sol[i][j];
}

long long n,i,j,A[10][10],B[10][10];
int main()
{
    f>>n;

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

    B[1][1]=0;
    B[1][2]=1;
    B[2][1]=1;
    B[2][2]=1;


    putere(n,B);
    inmultire(A,B);

    g<<A[1][1]%mod;
    return 0;
}