PalindORme solution codeforces

PalindORme solution codeforces

 

An integer array aa of length nn is said to be a PalindORme if (a1a1 || a2a2 ||  || ai)=(ani+1ai)=(an−i+1 ||  || an1an−1 || an)an) for all 1in1≤i≤n, where || denotes the bitwise OR operation.

An integer array aa of length nn is considered to be good if its elements can be rearranged to form a PalindORme. Formally, array aa is good if there exists a permutation p1,p2,pnp1,p2,…pn (an array where each integer from 11 to nn appears exactly once) for which ap1,ap2,apnap1,ap2,…apn is a PalindORme. PalindORme solution codeforces

Find the number of good arrays of length nn, consisting only of integers in the range [0,2k1][0,2k−1], and print it modulo some prime mm.

Two arrays a1,a2,,ana1,a2,…,an and b1,b2,,bnb1,b2,…,bn are considered to be different if there exists any ii (1in)(1≤i≤n) such that aibiai≠bi.

Input

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

Output PalindORme solution codeforces

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

Examples

input

Copy
1 1 998244353

output

Copy
2

input PalindORme solution codeforces

Copy
3 2 999999733

output

Copy
40

input

Copy
7 3 796735397

output PalindORme solution codeforces

Copy
1871528

input

Copy
2 46 606559127

output

Copy
177013
Note PalindORme solution codeforces

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 b=[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(l,r)OR(l,r) denotes blbl || bl+1bl+1 ||  || brbr

Leave a Comment