Дед Мазайкин – коллекционер мозаик-головоломок. Однажды он решил взять коробку и уложить в нее мозаики некоторым образом. Если взять квадрат размера k × k, разбитый на клетки размера 1 × 1 и закрасить в нем главную диагональ вместе с клетками, лежащими выше нее, то закрашенная область будет равна области, занимаемой одной мозаикой размера k. У Деда Мазайкина так же есть коробка с квадратным основанием 2n × 2n, разбитая на клетки размера 1 × 1. В коробке мозаики не должны перекрываться, и их нельзя переворачивать или поворачивать. На рисунках изображены мозаики размера 21, 22 и расположение мозаик в коробке для 23 (как в примере) соответственно:

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

Input format

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

Output format

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

173

251

Посмотреть ответы 1

Ответы на вопрос:

nastya05112

Информатика

4,5(7 оценок)

Устанавливаются все нужные файлы оп

Задай свой вопрос

Как otvet5GPT работает?

otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.
Сколько это стоит?

Проект находиться на стадии тестирования и все услуги бесплатны.
Могу ли я использовать otvet5GPT в школе?

Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!
В чем отличия от ChatGPT?

otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.