A. Печеньки
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Клычок — коллекционер печенек. Однажды он решил взять коробку и уложить в нее печеньки некоторым образом. Если взять квадрат размера k × k, разбитый на клетки размера 1 × 1 и закрасить в нем главную диагональ вместе с клетками, лежащими выше нее, то закрашенная область будет равна области, занимаемой одной печенькой размера k. У Клычка так же есть коробка с квадратным основанием 2n × 2n, разбитая на клетки размера 1 × 1. В коробке печеньки не должны перекрываться, и их нельзя переворачивать или поворачивать. На рисунках изображены печеньки размера 2 и 4 соответственно:

Для укладки печенек маленький морж использует следующий алгоритм. Он берет из хранилища самую большую печеньку, которая может поместиться на некоторое место в коробке, и кладет ее туда. Все бы хорошо, но у маленького моржа в хранилище есть бесконечно много печенек размера 2 и больше, а печеньки размера 1 отсутствуют, следовательно, в коробке останутся пустые клетки. Его интересует, сколько же пустых клеток окажется в итоге.

Входные данные

В первой строке записано единственное целое число n (0 ≤ n ≤ 1000).

Выходные данные

Выведите единственное число, равное количеству пустых клеток в коробке. Ответ следует вывести по модулю 106 + 3.

Примеры
Входные данные
3
Выходные данные
9
Примечание

Если коробка имеет основание 23 × 23 (как в примере), то печеньки в нее будут уложены следующим образом: