Целочисленный массив \(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\).
Выходные данные
Выведите одно целое число — количество хороших массивов по модулю \(m\).
Примечание
В первом примере оба возможных массива \([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}\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1 998244353
|
2
|
|
2
|
3 2 999999733
|
40
|
|
3
|
7 3 796735397
|
1871528
|
|
4
|
2 46 606559127
|
177013
|