整数 $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$ には $1$ がちょうど $X$ 個、$2$ がちょうど $Y$ 個含まれる。
- $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
注記
1つ目の例では、条件を満たす三つ組 $(A, B, C)$ は $24$ 個あります。例えば、$A = (1, 2, 3)$、$B = (3, 3, 2)$、$C = (2, 1, 1)$ とすると、$(A, B, C)$ はすべての条件を満たします。