PalindORme

题意翻译

称一个长度为 $n$ 的序列 $a$ 是 $\text{PalindORme}$ 的，当且仅当对于任意 $1 \le i \le n$，满足 $a_1 | a_2 | \dots | a_i = a_n | a_{n-1} | \dots |a_{n-i+1}$，其中 `|` 表示按位或运算。 称一个长度为 $n$ 的序列 $b$ 是 $\text{good}$ 的，当且仅当它可以重排成一个 $\text{PalindORme}$ 的序列。 给你 $n,k,m$，求长度为 $n$，每个元素值域为 $[0,2^k)$ 的序列中有多少个是 $\text{good}$ 的，对 $m$ 取模。

题目描述

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](https://en.wikipedia.org/wiki/Bitwise_operation#OR). 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 $ .

输入输出样例

输入样例 #1

1 1 998244353

输出样例 #1

2

输入样例 #2

3 2 999999733

输出样例 #2

40

输入样例 #3

7 3 796735397

输出样例 #3

1871528

输入样例 #4

2 46 606559127

输出样例 #4

177013

说明

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} $