PalindORme
Description
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$.
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.
Print a single integer — the number of good arrays modulo $m$.
Input
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.
Output
Print a single integer — the number of good arrays modulo $m$.
Samples
1 1 998244353
2
3 2 999999733
40
7 3 796735397
1871528
2 46 606559127
177013
Note
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}$