Комната имеет прямоугольную форму размером M × N (1 ≤ M ≤ 9, 1 ≤ N ≤ 9) . Необходимо уложить его паркетом. Есть деревяшки двух форм:

• прямоугольники (2 × 1)
• уголки (квадрат 2 × 2 без одного куска 1 × 1 )

Вы должны найти X — количество способов покрыть пол паркетом (не должно остаться пустых мест; части не должны накладываться друг на друга и выходить за границу комнаты).

Рассмотрим один специальный тип двоичных деревьев поиска, который часто называют "декартовым деревом". Напомним, что двоичным деревом поиска называется двоичное дерево, в каждой вершине которого записан некоторый ключ (в этой задаче ключ представляет собой целое число), причем для каждой вершины u выполнены следующие условия: все ключи в левом поддереве u меньше чем ключ в вершине u , а все ключи в правом поддереве - больше. Будем называть двоичное дерево поиска декартовым деревом, если в каждой вершине u помимо основного ключа х _u хранится также вспомогательный ключ y _u , причем для этих ключей выполнено "условие кучи": если v - родитель u , то y _v < y _u . Будем называть множество пар ( x ₁ , y ₁ ), ( х ₂ , y ₂ ), ... ( х _n , у _n ) корректным , если все x _i – различные числа от 1 до n , и то же условие выполнено для y _i . Легко показать, что для любого корректного множества пар существует в точности одно декартово дерево, которое содержит пары из заданного множества в качестве пар ключей. Рассмотрим двоичное дерево T с n вершинами. Ваша задача - найти количество различных корректных множеств пар, таких что их можно расставить в вершинах T . чтобы превратить его в декартово дерево. Например, для дерева, приведенного на рисунке, существует три соответствующих корректных множества пар: {(1, 2), (2, 3), (3, 1), (4, 4)}, {(1, 2), (2, 4), (3, 1), (4, 3)} и {(1, 3), (2, 4), (3, 1), (4, 2)}.

Андрей Сергеевич работает воспитателем в детском саду. Недавно он придумал новую веселую игру, для участия в которой все дети разбились на n команд. В качестве призов для участников игры Андрей Сергеевич подготовил d конфет.

По итогам игры оказалось, что в команде, занявшей i -е место, ровно x _i участников.

Теперь перед Андреем Сергеевичем стоит непростая задача: надо распределить конфеты. При этом должны выполняться следующие условия:

• Все участники одной команды должны получить поровну конфет: пусть участники команды, занявшей i -е место получат по a _i конфет;
• Каждый ребенок должен получить хотя бы одну конфету: a _i > 0 ;
• Участники команды, занявшей более высокое место, должны получить больше конфет: если i < j , то a _i > a _j
• Все конфеты должны быть распределены: a _{1 x 1} + a _{2 x 2} + ... a _{nx n} = d

Алла очень любит палиндромы. Все потому, что её имя является палиндромом. Напомним, что строку называют палиндромом тогда, когда она одинаково читается как слева направо, так и справа налево.

Однажды в школе учитель рассказал Алле про так называемые строки Фибоначчи. Строки Фибоначчи определяются следующим образом:

• f ₀ = a
• f ₁ = b
• f _n = f _{n −1} f _{n −2} для каждого n ≥ 2 — конкатенация двух предыдущих строк Фибоначчи

Аллу сразу заинтересовал вопрос — какой максимально длинный палиндром встречается в k -й строке Фибоначчи. Помогите Алле решить эту задачу.

В одном квадратном государстве жили квадратные люди. И все остальное в этом государстве было тоже квадратное. Так, Квадратная Дума приняла Квадратный Закон о земле. Согласно этому закону, любой житель государства имел право приобрести землю. Земля продавалась, естественно, квадратными участками. Длина стороны каждого участка выражалась натуральным числом метров. Приобретая участок земли со стороной a метров, покупатель платил a ² квадриков (местная валюта) и получал одно квадратное свидетельство о праве собственности на этот участок. Один житель этого государства решил вложить все свои N квадриков без остатка в покупку земли. Это безусловно можно было сделать, приобретя участки размером 1 * 1 метр. Но этот житель потребовал от агентства недвижимости минимизации количества покупаемых участков. «Так мне будет легче общаться с Квадратной Налоговой Инспекцией», - сказал он. Сделка состоялась.

Найдите, какое количество квадратных свидетельств он получил.