#include <iostream>
#include <fstream>
#define Q 666013

using namespace std;

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

int k,v[100],n;

void prod(int c[3][3],int m1[3][3],int m2[3][3])
{
    c[1][1]=(m1[1][1]*m2[1][1]+m1[1][2]*m2[2][1])%Q;
    c[1][2]=(m1[1][1]*m2[1][2]+m1[1][2]*m2[2][2])%Q;
    c[2][1]=(m1[2][1]*m2[1][1]+m1[2][2]*m2[2][1])%Q;
    c[2][2]=(m1[2][1]*m2[1][2]+m1[2][2]*m2[2][2])%Q;
}

void init()
{
    while(k>1)
    {
        n++;
        if(k%2==0)
		{
			k=k/2;
            v[n]=1;
		}
        else
		{
			k--;
            v[n]=2;
		}
    }
}

void put()
{
    int i,sol[3][3],c[3][3],aux[3][3];
    init();
	
	sol[1][1]=0;
	sol[1][2]=sol[2][1]=sol[2][2]=1;
	
	c[1][1]=0;
	c[1][2]=c[2][1]=c[2][2]=1;
	
	for(i=n;i>=1;i--)
	{
		if(v[i]==1)
			prod(aux,sol,c);
		
		if(v[i]==2)
			prod(aux,sol,sol);
		
		sol[1][1]=aux[1][1];
		sol[1][2]=aux[1][2];
		sol[2][1]=aux[2][1];
		sol[2][2]=aux[2][2];
	}
	fout<<sol[1][1];
}

int main()
{
    fin>>k;
	put();
    return 0;
}