#include <stdlib.h>
#include <cmath>
#include <iostream>
#include <stdio.h>
#include <string.h>
#define Modulo 666013


using namespace std;

long long dest[2][2];
long long ident[2][2];
long long prod[2][2];
void mult(long long a[2][2], long long b[2][2])
{
	long long c[2][2];
	long long val = 0;
	for (int i=0;i<2;i++)
		for (int j=0;j<2;j++)
		{

			for (int k=0;k<2;k++)
				val += ( (a[i][k] % Modulo ) * ( b[k][j] % Modulo) % Modulo );
			c[i][j] = val % Modulo;
			val = 0;
		}

	for (int i=0;i<2;i++)
		for (int j=0;j<2;j++)
		{
			prod[i][j] = c[i][j];
		}
}

void power(long long p )
{
    for(; p; p/=2)
    {

    if(p%2==1)
    {
        mult(ident,dest);
        memcpy(ident,prod,sizeof(prod));

    }

    mult(dest,dest);
    memcpy(dest,prod,sizeof(prod));
    }
}

int main(int argc, char *argv[])
{
    long long n;
	dest[0][0] = 0;
	dest[0][1] = dest[1][0] = dest[1][1] = 1;

	ident[0][0] = ident[1][1] = 1;
	ident[1][0] = ident[0][1] = 0;

	FILE *File1 = fopen("kfib.in","r");
    fscanf(File1,"%lld",&n);

	power(n-1);
	FILE *File2 = fopen("kfib.out","w");
	fprintf(File2,"%lld",ident[1][1]);

	return 0;
}