F. ПалиндORм
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Целочисленный массив $$$a$$$ длины $$$n$$$ называется палиндORмом, если ($$$a_{1}$$$ $$$|$$$ $$$a_{2} $$$ $$$|$$$ $$$ \ldots $$$ $$$|$$$ $$$ a_{i}) = (a_{{n - i + 1}} $$$ $$$|$$$ $$$ \ldots $$$ $$$|$$$ $$$ a_{{n - 1}} $$$ $$$|$$$ $$$ a_{n}) $$$ для всех $$$ 1 \leq i \leq n$$$, где $$$|$$$ обозначает операцию побитового ИЛИ.

Целочисленный массив $$$a$$$ длины $$$n$$$ считается хорошим, если его элементы могут быть переставлены так, чтобы образовать палиндORм. Формально, массив $$$a$$$ является хорошим, если существует перестановка $$$p_1, p_2, \ldots p_n$$$ (массив, в котором каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно один раз), для которой $$$a_{p_1}, a_{p_2}, \ldots a_{p_n}$$$ является палиндORмом.

Найдите количество хороших массивов длины $$$n$$$, состоящих только из целых чисел в диапазоне $$$[0, 2^{k} - 1]$$$, и выведите его по модулю некоторого простого числа $$$m$$$.

Два массива $$$a_1, a_2, \ldots, a_n$$$ и $$$b_1, b_2, \ldots, b_n$$$ считаются различными, если существует индекс $$$i$$$ $$$(1 \leq i \leq n)$$$ такой, что $$$a_i \ne b_i$$$.

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

Первая и единственная строка входных данных содержит три целых числа $$$n$$$, $$$k$$$ и $$$m$$$ ($$$1 \leq n,k \leq 80$$$, $$$10^8 \lt m \lt 10^9$$$). Гарантируется, что $$$m$$$ является простым.

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

Выведите одно целое число  — количество хороших массивов по модулю $$$m$$$.

Примеры
Входные данные
1 1 998244353
Выходные данные
2
Входные данные
3 2 999999733
Выходные данные
40
Входные данные
7 3 796735397
Выходные данные
1871528
Входные данные
2 46 606559127
Выходные данные
177013
Примечание

В первом примере оба возможных массива $$$[0]$$$ и $$$[1]$$$ являются хорошими.

Во втором примере есть несколько примеров хороших массивов:

  • $$$[2, 1, 2]$$$, потому что он уже является палиндORмом.
  • $$$[1, 1, 0]$$$, потому что его можно перестроить в $$$[1, 0, 1]$$$, что является палиндORмом.

Обратите внимание, что $$$[1, 1, 0]$$$, $$$[1, 0, 1]$$$ и $$$[0, 1, 1]$$$ являются хорошими массивами и считаются разными в соответствии с определением в утверждении.

В третьем примере примером хорошего массива является $$$[1, 0, 1, 4, 2, 5, 4]$$$. Его можно переставить в массив $$$b = [1, 5, 0, 2, 4, 4, 1]$$$, который является палиндORмом, потому что:

  • $$$\mathrm{OR}(1, 1)$$$ = $$$\mathrm{OR}(7, 7)$$$ = $$$1$$$
  • $$$\mathrm{OR}(1, 2)$$$ = $$$\mathrm{OR}(6, 7)$$$ = $$$5$$$
  • $$$\mathrm{OR}(1, 3)$$$ = $$$\mathrm{OR}(5, 7)$$$ = $$$5$$$
  • $$$\mathrm{OR}(1, 4)$$$ = $$$\mathrm{OR}(4, 7)$$$ = $$$7$$$
  • $$$\mathrm{OR}(1, 5)$$$ = $$$\mathrm{OR}(3, 7)$$$ = $$$7$$$
  • $$$\mathrm{OR}(1, 6)$$$ = $$$\mathrm{OR}(2, 7)$$$ = $$$7$$$
  • $$$\mathrm{OR}(1, 7)$$$ = $$$\mathrm{OR}(1, 7)$$$ = $$$7$$$

Здесь $$$\mathrm{OR}(l, r)$$$ обозначает $$$b_{l}$$$ $$$|$$$ $$$b_{l+1} $$$ $$$|$$$ $$$ \ldots $$$ $$$|$$$ $$$ b_{r}$$$