← 返回题目列表

Codeforces · 1605/F

F. 回文

中文机器翻译题面 查看原题

如果 ($$$a_{1}$$$ $$$|$$$ $$$a_{2} $$$ $$$|$$$ $$$ \ldots $$$ $$$|$$$ $$$ a_{i}) = (a_{{n - i + 1}} $$$ $$$|$$$ $$$ \ldots $$$ $$$|$$$ $$$ a_{{n - 1}} $$$ $$$|$$$ $$$ a_{n}) $$$ 对于所有 $$$ 1 \leq i \leq n$$$,其中 $$$|$$$ 表示按位 OR 运算。

如果长度为 $$$n$$$ 的整数数组 $$$a$$$ 被认为是好的,如果它的元素可以重新排列以形成 PalindORme。形式上,如果存在一个排列 $$$p_1, p_2, \ldots p_n$$$(从 $$$1$$$ 到 $$$n$$$ 的每个整数只出现一次的数组),其中 $$$a_{p_1}, a_{p_2}, \ldots a_{p_n}$$$ 是回文数组,则数组 $$$a$$$ 是好的。

查找长度为 $$$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$$$ 被认为是不同的。

输入

输入的第一行也是唯一一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$m$$$ ($$$1 \leq n,k \leq 80$$$、$$$10^8 \lt m \lt 10^9$$$)。保证 $$$m$$$ 是素数。

输出

打印一个整数——好数组的数量以 $$$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

注意

在第一个示例中,可能的数组 $$$[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}$$$