import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Computes the nth element from the Fibonacci sequence, modulo 666013.
 *
 * @author Andrei Muntean
 */
public class Main
{
	static int[] f = new int[]
	{
		0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
	};

	// f[x - 2].
	static long fx_2;

	// f[x - 1].
	static long fx_1;

	// f[x].
	static long fx;

	// f[x + 1].
	static long fx1;

	// This is written in Ancient Norse.
	private static int fibonacci(int x, int n)
	{
		if (2 * x - 2 <= n)
		{	
			// f[2x - 2] = f[x - 1] * (f[x - 2] + f[x]).
			fx_2 = (fx_1 * (fx_2 + fx)) % 666013;

			// f[2x] = f[x] * (f[x - 1] + f[x + 1]).
			fx = (fx * (fx_1 + fx1)) % 666013;

			// f[2x - 1] = f[2x] - f[2x - 2].
			fx_1 = Math.floorMod(fx - fx_2, 666013);

			// f[2x + 1] = f[2x - 1] + f[2x].
			fx1 = (fx_1 + fx) % 666013;

			return fibonacci(2 * x, n);
		}
		else if (n == x - 2)
		{
			return (int)fx_2;
		}
		else if (n == x - 1)
		{
			return (int)fx_1;
		}
		else if (n == x)
		{
			return (int)fx;
		}
		else if (n == x + 1)
		{
			return (int)fx1;
		}
		else
		{
			while (x++ < n)
			{
				long fx_1New = fx;

				// f[x + 1] = f[x] + f[x - 1].
				fx = (fx + fx_1) % 666013;

				// Updates f[x - 1] to be f[x].
				fx_1 = fx_1New;
			}

			return (int)fx;
		}
	}

	// Returns the Fibonacci number at the specified index, modulo 666013.
	public static int get(int index)
	{
		if (index < f.length)
		{
			return f[index];
		}
		else
		{
			int x = index;

			while (x > 10)
			{
				x /= 2;
			}

			fx_2 = f[x - 2];
			fx_1 = f[x - 1];
			fx = f[x];
			fx1 = f[x + 1];

			return fibonacci(x, index);
		}
	}

	public static void main(String[] args) throws IOException
	{
		if (args.length == 1)
		{
			System.out.println(get(Integer.parseInt(args[0])));
		}
		else
		{
			int index = 0;
			int result = 0;

			try (Scanner scanner = new Scanner(new FileReader("kfib.in")))
			{
				index = scanner.nextInt();
			}

			result = get(index);

			try (PrintWriter printWriter = new PrintWriter(new FileWriter("kfib.out")))
			{
				printWriter.println(result);
			}
		}
	}
}