Time Limit: 3000/1500 MS (Java/Others)

Memory Limit: 524288/524288 K (Java/Others)


$Hazel$ would like to find out everything about the binary tree.
She has a **full** binary tree ,each point has different labels.
regarding each point of tree ,$Hazel$ defines its height $h_i$ being the number of points which the shortest path from this point to a leaf has.
each point has weight $A_i$ which be defined as $X^{h_i}$.
$Hazel$ wants to paint every points by color $B_i$,Observing the following rules:
$\bullet\ \forall i\in T,B_i\in N$
$\bullet\ \forall i\in T,B_i\ge B_{fa_i}$
$\bullet\ Y\ge 2\times \sum_{i\in leaf} B_i-\sum_{i\in T}B_i$
(define $B_{fa_{root}}=0$ )
$Hazel$ defines the contribution of the tree $S$ as $\sum_{i\in T}A_i\times B_i$.
She wants to know how many legal methods can she paint the tree,which cause $S$ is multiple of $P$.
You need to print $ans \ mod (10^9+7)$.


4 positive integer$H$,$X$,$Y$,$P$($1\le H\le 10^{18}$,$1\le X\le 500$,$0\le Y\le 10$,$1\le P\le 500$,$P$ is a prime number).
$H$means the tree has$2^H-1$ points.


an integer showing $ans \ mod (10^9+7)$.

Sample Input

2 8 10 7 11 34819237827249996 146 5 349

Sample Output

630072624 673102984




2017 Multi-University Training Contest - Te