Codeforces Round 754 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

*2900

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. PalindORme

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAn 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$$$.

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

Examples

Input

1 1 998244353

Output

2

Input

3 2 999999733

Output

40

Input

7 3 796735397

Output

1871528

Input

2 46 606559127

Output

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/09/2024 08:41:36 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|