# [Solution] PalindORme solution codeforces

## PalindORme solution codeforces

An integer array 𝑎a of length 𝑛n is said to be a PalindORme if (𝑎1a1 || 𝑎2a2 ||  || 𝑎𝑖)=(𝑎𝑛𝑖+1ai)=(an−i+1 ||  || 𝑎𝑛1an−1 || 𝑎𝑛)an) for all 1𝑖𝑛1≤i≤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 𝑝1,𝑝2,𝑝𝑛p1,p2,…pn (an array where each integer from 11 to 𝑛n appears exactly once) for which 𝑎𝑝1,𝑎𝑝2,𝑎𝑝𝑛ap1,ap2,…apn is a PalindORme.

Find the number of good arrays of length 𝑛n, consisting only of integers in the range [0,2𝑘1][0,2k−1], and print it modulo some prime 𝑚m.

## PalindORme solution codeforces

Two arrays 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an and 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn are considered to be different if there exists any 𝑖i (1𝑖𝑛)(1≤i≤n) such that 𝑎𝑖𝑏𝑖ai≠bi.

Input

The first and only line of the input contains three integers 𝑛n𝑘k and 𝑚m (1𝑛,𝑘801≤n,k≤80108<𝑚<109108<m<109). It is guaranteed that 𝑚m is prime.

Output

Print a single integer  — the number of good arrays modulo 𝑚m.

## PalindORme solution codeforces

Examples

input

Copy
1 1 998244353

output

Copy
2


## PalindORme solution codeforces

input

Copy
3 2 999999733

output

Copy
40

input

Copy
7 3 796735397

output

Copy
1871528


## PalindORme solution codeforces

input

Copy
2 46 606559127

output

Copy
177013


## PalindORme solution codeforces

Note

In the first sample, both the possible arrays  and  are good.

In the second sample, some examples of good arrays are:

• [2,1,2][2,1,2] because it is already PalindORme.
• [1,1,0][1,1,0] because it can rearranged to [1,0,1][1,0,1] which is PalindORme

Note that [1,1,0][1,1,0][1,0,1][1,0,1] and [0,1,1][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][1,0,1,4,2,5,4]. It can be rearranged to an array 𝑏=[1,5,0,2,4,4,1]b=[1,5,0,2,4,4,1] which is a PalindORme because:

• OR(1,1)OR(1,1) = OR(7,7)OR(7,7) = 11
• OR(1,2)OR(1,2) = OR(6,7)OR(6,7) = 55
• OR(1,3)OR(1,3) = OR(5,7)OR(5,7) = 55
• OR(1,4)OR(1,4) = OR(4,7)OR(4,7) = 77
• OR(1,5)OR(1,5) = OR(3,7)OR(3,7) = 77
• OR(1,6)OR(1,6) = OR(2,7)OR(2,7) = 77
• OR(1,7)OR(1,7) = OR(1,7)OR(1,7) = 77

Here OR(𝑙,𝑟)OR(l,r) denotes 𝑏𝑙bl || 𝑏𝑙+1bl+1 ||  || 𝑏𝑟    