給定整數 $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)$ 滿足所有條件。