#include <bits/stdc++.h>

using namespace std;
#define MODULO 666013

ifstream f1("kfib.in");
ofstream f2("kfib.out");

long long int a[2][2]={1,0,0,1} , b[2][2]={0,1,1,1} , c[2][2]={1,1,0,0};

long long int n;

void inmultire_matrice(long long int A[][2] , long long int B[][2])
{
    long long int C[2][2];
    for(int i=0 ; i<2 ; i++)
    {
        for(int j=0 ; j<2 ; j++)
        {
            C[i][j]=0;
            for(int k=0 ; k<2 ; k++)
            {
                C[i][j]=(C[i][j]+A[i][k]*B[k][j])%MODULO;
            }
        }
    }
    for(int i=0; i<2; i++)
    {
        for(int j=0; j<2; j++)
        {
            A[i][j]=C[i][j];
        }
    }
}

void exp_log(long long int n)
{
    while(n>0)
    {
        if(n%2==0)
        {
            n=n/2;
            inmultire_matrice(b,b);
        }
        else
        {
            n--;
            inmultire_matrice(a,b);
        }
    }
}

int main()
{
    f1 >> n;
    exp_log(n-1);
    inmultire_matrice(c , a);
    f2 << c[0][0];
    return 0;
}