You are given integers $N, X, Y, K$, and $M$. Find the number of triples $(A, B, C)$ of integer sequences of length $N$ that satisfy all of the following conditions, modulo $M$.
- For each $i = 1, 2, \dots, N$, the tuple $(A_i, B_i, C_i)$ is a permutation of $(1, 2, 3)$.
- The sequence $A$ contains exactly $X$ occurrences of $1$ and $Y$ occurrences of $2$.
- The sum of the number of inversions of $A$, $B$, and $C$ is equal to $K$.
Here, the number of inversions of a sequence $a$ is defined as the number of pairs of integers $(i, j)$ satisfying $1 \le i < j \le |a|$ and $a_i > a_j$.
Input
The input is given in the following format:
N X Y K M
- All input values are integers.
- $2 \le N \le 50$.
- $0 \le X, Y \le N$.
- $X + Y \le N$.
- $0 \le K \le \frac{3}{2}N(N - 1)$.
- $10^8 \le M \le 10^9$.
Output
Print the answer.
Sample 1
3 1 1 4 998244353
24
Sample 2
4 0 0 18 123456789
0
Sample 3
50 10 20 1000 1000000000
805988728
Note
In the first example, there are $24$ triples $(A, B, C)$ that satisfy the conditions. For example, if we take $A = (1, 2, 3)$, $B = (3, 3, 2)$, and $C = (2, 1, 1)$, then $(A, B, C)$ satisfies all the conditions.