import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.util.Scanner;


public class KthFibonacci {
	public static int k;
	public static int modulo=666013;
	public static void readInput()
	{
		Scanner scanner = null;
		try
		{
			scanner = new Scanner(new File("kfib.in"));
			k = scanner.nextInt();
			
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
		finally
		{
			try
			{
				if (scanner!=null)
					scanner.close();
			}
			catch (Exception e)
			{
				e.printStackTrace();
			}
		}
	}
	public static int[][] matrixPower(int[][] matrix, int power)
	{
		if (power == 1)
			return matrix;
		else
		{
			int n = matrix.length;
			int[][] P = new int[n][n];
			P = matrixPower(matrix , (int)power/2);
			if (power % 2 == 0)
			{
				return matrixMultiply(P,P);
			}
			return matrixMultiply(matrixMultiply(P,P),matrix);
		}
	}
	public static int[][] matrixMultiply(int[][] a, int[][] b)
	{
		int m = a.length;
		int n = a[0].length;
		int p = b[0].length;
		int[][] result = new int[m][p];
		for (int i=0; i<m; i++)
			for (int j=0; j<p; j++)
			{
				int s = 0;
				for (int k=0; k<n; k++)
				{
					s += a[i][k]*b[k][j];
				}
				result[i][j] = s%modulo;
			}
		return result;
	}
	public static int kthFib()
	{
		int[][] initial = new int[1][2];
		int[][] fin = new int[1][2];
		int[][] A = { {0,1} , {1,1} };
		initial[0][0] = 0;
		initial[0][1] = 1;
		fin = matrixMultiply(initial,matrixPower(A,k-1));
		return fin[0][1];
	}
	public static void printMatrix(int[][] matrix)
	{
		int m = matrix.length;
		int n = matrix[0].length;
		for (int i=0; i<m; i++)
		{
			for (int j=0; j<n; j++)
				System.out.print(matrix[i][j] + " ");
			System.out.println("");
		}
		
	}
	public static void writeOutput()
	{
		try
		{
			BufferedWriter output = new BufferedWriter(new FileWriter("kfib.out"));
			output.write(kthFib());
			output.close();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
		
	}
	public static void main(String args[])
	{
		System.out.println(kthFib());
	}
}