Mystery

Problem Description

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

Input

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.

Output

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

Sample Input

2

8 10 7 11

34819237827249996 146 5 349

Sample Output

630072624

673102984

Source

2017 Multi-University Training Contest - Team 7

https://acm.hdu.edu.cn/showproblem.php?pid=6132