CF1605F PalindORme

一个长度为 $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)$，其中 $|$ 表示[按位或运算](https://en.wikipedia.org/wiki/Bitwise_operation#OR)。 如果一个长度为 $n$ 的整数数组 $a$ 的元素可以重新排列成一个 PalindORme，则称该数组是好的。形式化地说，如果存在一个排列 $p_1, p_2, \ldots, p_n$（一个 $1$ 到 $n$ 的排列），使得 $a_{p_1}, a_{p_2}, \ldots, a_{p_n}$ 是 PalindORme，则称数组 $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 < m < 10^9$）。保证 $m$ 是质数。

输出一个整数，表示好的数组的个数，对 $m$ 取模。

在第一个样例中，所有可能的数组 $[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 \mid b_{l+1} \mid \ldots \mid b_r$。 由 ChatGPT 4.1 翻译