Bạn được cho các số nguyên $N, X, Y, K$ và $M$. Hãy tìm số lượng bộ ba $(A, B, C)$ gồm các dãy số nguyên có độ dài $N$ thỏa mãn tất cả các điều kiện sau, theo modulo $M$:
- Với mỗi $i = 1, 2, \dots, N$, bộ ba $(A_i, B_i, C_i)$ là một hoán vị của $(1, 2, 3)$.
- Dãy $A$ chứa đúng $X$ số $1$ và $Y$ số $2$.
- Tổng số lượng cặp nghịch thế của $A$, $B$ và $C$ bằng $K$.
Ở đây, số lượng cặp nghịch thế của một dãy $a$ được định nghĩa là số lượng cặp số nguyên $(i, j)$ thỏa mãn $1 \le i < j \le |a|$ và $a_i > a_j$.
Dữ liệu vào
Dữ liệu vào được cho theo định dạng sau:
N X Y K M
- Tất cả các giá trị đầu vào đều là số nguyên.
- $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$.
Dữ liệu ra
In ra đáp án.
Ví dụ 1
3 1 1 4 998244353
24
Ví dụ 2
4 0 0 18 123456789
0
Ví dụ 3
50 10 20 1000 1000000000
805988728
Ghi chú
Trong ví dụ thứ nhất, có $24$ bộ ba $(A, B, C)$ thỏa mãn các điều kiện. Ví dụ, nếu ta chọn $A = (1, 2, 3)$, $B = (3, 3, 2)$ và $C = (2, 1, 1)$, thì $(A, B, C)$ thỏa mãn tất cả các điều kiện.