[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 [0][0] and [1][1] 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 ||  || 𝑏𝑟


PalindORme solution codeforcesYet another MEX problem solution codechefYet another MEX problem solution codechefYet another MEX problem solution codechef

Leave a Comment

Your email address will not be published. Required fields are marked *