俾整數 $N, X, Y, K$ 同 $M$。求滿足以下所有條件嘅長度為 $N$ 嘅整數序列三元組 $(A, B, C)$ 嘅數量,對 $M$ 取模嘅結果。
- 對於每個 $i = 1, 2, \dots, N$,三元組 $(A_i, B_i, C_i)$ 係 $(1, 2, 3)$ 嘅一個排列。
- 序列 $A$ 啱啱好包含 $X$ 個 $1$ 同埋 $Y$ 個 $2$。
- $A$、$B$ 同 $C$ 嘅逆序對數量之和等於 $K$。
喺度,一個序列 $a$ 嘅逆序對數量定義為滿足 $1 \le i < j \le |a|$ 且 $a_i > a_j$ 嘅整數對 $(i, j)$ 嘅數量。
輸入格式
輸入按以下格式俾出:
N X Y K M
- 所有輸入值都係整數。
- $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$.
輸出格式
輸出答案。
樣例 1
3 1 1 4 998244353
24
樣例 2
4 0 0 18 123456789
0
樣例 3
50 10 20 1000 1000000000
805988728
樣例說明
喺第一個樣例入面,有 $24$ 個滿足條件嘅三元組 $(A, B, C)$。例如,如果我哋取 $A = (1, 2, 3)$、$B = (3, 3, 2)$ 同埋 $C = (2, 1, 1)$,咁 $(A, B, C)$ 就滿足所有條件。