#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <climits>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <iomanip>
#include <stack>
#include <cstdio>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

void inmulteste(int* c[2], int* d[2]);
void creeaza( int exp);

#define baza 10
#define MAX 501000

const long long int MOD=666013;
long long int a[2][2],b[2][2];

void inmulteste(long long int c[][2], long long int d[][2])
{
    long long int a00=((c[0][0]*d[0][0])+(c[0][1]*d[1][0]))%MOD;
    long long int a01=((c[0][0]*d[0][1])+(c[0][1]*d[1][1]))%MOD;
    long long int a10=((c[1][0]*d[0][0])+(c[1][1]*d[1][0]))%MOD;
    long long int a11=((c[1][0]*d[0][1])+(c[1][1]*d[1][1]))%MOD;
    //a01=a10;
    //a11=a00-a01;
    c[0][0]=a00;
    c[0][1]=a01;
    c[1][0]=a10;
    c[1][1]=a11;
}

void creeaza(long long int exp)
{
    b[0][1]=b[1][0]=0;
    b[1][1]=b[0][0]=1;
    while(exp)
    {
        if(exp&1)
        {
            inmulteste(b,a);
        }
        inmulteste(a,a);
        exp>>=1;
    }
}

int main()
{
    long long int n;
    a[0][0]=a[1][0]=a[0][1]=1;
    fin>>n;
    creeaza(n);
    fout<<b[0][1];



    return 0;
}