CF1605F.PalindORme

An integer array $a$ of length $n$ is said to be a PalindORme if ($a_{1}$ $|$ $a_{2} $ $|$ $ \ldots $ $|$ $ a_{i}) = (a_{{n - i + 1}} $ $|$ $ \ldots $ $|$ $ a_{{n - 1}} $ $|$ $ a_{n}) $ for all $ 1 \leq i \leq n$, where $|$ denotes the bitwise OR operation.

An integer array $a$ of length $n$ is considered to be good if its elements can be rearranged to form a PalindORme. Formally, array $a$ is good if there exists a permutation $p_1, p_2, \ldots p_n$ (an array where each integer from $1$ to $n$ appears exactly once) for which $a_{p_1}, a_{p_2}, \ldots a_{p_n}$ is a PalindORme.

Find the number of good arrays of length $n$, consisting only of integers in the range $[0, 2^{k} - 1]$, and print it modulo some prime $m$.

Two arrays $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$ are considered to be different if there exists any $i$ $(1 \leq i \leq n)$ such that $a_i \ne b_i$.

长度为 $n$ 的整数数组 $a$ 被称为 PalindORme（“或回文”），当且仅当对所有 $1 \leq i \leq n$，均满足

$$(a_{1} \mid a_{2} \mid \ldots \mid a_{i}) = (a_{{n - i + 1}} \mid \ldots \mid a_{{n - 1}} \mid a_{n}),$$

其中 $\mid$ 表示按位或运算。

长度为 $n$ 的整数数组 $a$ 被称为 好数组（good array），如果其元素可以重排后构成一个 PalindORme。形式化地说，数组 $a$ 是好数组，当且仅当存在一个排列 $p_1, p_2, \ldots, p_n$（即 $1$ 到 $n$ 的每个整数在该数组中恰好出现一次），使得重排后的数组 $a_{p_1}, a_{p_2}, \ldots, a_{p_n}$ 是一个 PalindORme。

求长度为 $n$、且每个元素均属于区间 $[0, 2^{k} - 1]$ 的好数组的个数，并将结果对某个质数 $m$ 取模后输出。

若存在某个下标 $i$（$1 \leq i \leq n$）使得 $a_i \ne b_i$，则称两个数组 $a_1, a_2, \ldots, a_n$ 与 $b_1, b_2, \ldots, b_n$ 不同。

The first and only line of the input contains three integers $n$, $k$ and $m$ ($1 \leq n,k \leq 80$, $10^8 \lt m \lt 10^9$). It is guaranteed that $m$ is prime.

输入仅有一行，包含三个整数 $n$、$k$ 和 $m$（$1 \leq n,k \leq 80$，$10^8 \lt m \lt 10^9$）。保证 $m$ 是质数。

Print a single integer — the number of good arrays modulo $m$.

输出一个整数——好数组的个数对 $m$ 取模的结果。

In the first sample, both the possible arrays $[0]$ and $[1]$ are good.

In the second sample, some examples of good arrays are:

• $[2, 1, 2]$ because it is already PalindORme.
• $[1, 1, 0]$ because it can rearranged to $[1, 0, 1]$ which is PalindORme

Note that $[1, 1, 0]$, $[1, 0, 1]$ and $[0, 1, 1]$ are all good arrays and are considered to be different according to the definition in the statement.

In the third sample, an example of a good array is $[1, 0, 1, 4, 2, 5, 4]$. It can be rearranged to an array $b = [1, 5, 0, 2, 4, 4, 1]$ which is a PalindORme because:

• $\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$

Here $\mathrm{OR}(l, r)$ denotes $b_{l}$ $|$ $b_{l+1} $ $|$ $ \ldots $ $|$ $ b_{r}$

在第一个样例中，两个可能的数组 $[0]$ 和 $[1]$ 均为好数组。

在第二个样例中，一些好数组的例如下：

• $[2, 1, 2]$，因为它本身已是 PalindORme；
• $[1, 1, 0]$，因为它可重排为 $[1, 0, 1]$，而后者是 PalindORme。

注意：根据题目陈述中的定义，$[1, 1, 0]$、$[1, 0, 1]$ 和 $[0, 1, 1]$ 均为好数组，且被视为互不相同的数组。

在第三个样例中，一个好数组的例子是 $[1, 0, 1, 4, 2, 5, 4]$。它可以被重排为数组 $b = [1, 5, 0, 2, 4, 4, 1]$，该数组是一个 PalindORme，因为：

• $\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}$。