Anda diberikan bilangan bulat $N, X, Y, K$, dan $M$. Carilah banyaknya tripel $(A, B, C)$ dari barisan bilangan bulat dengan panjang $N$ yang memenuhi semua kondisi berikut, modulo $M$.
- Untuk setiap $i = 1, 2, \dots, N$, tupel $(A_i, B_i, C_i)$ adalah permutasi dari $(1, 2, 3)$.
- Barisan $A$ memuat tepat $X$ kemunculan angka $1$ dan $Y$ kemunculan angka $2$.
- Jumlah dari banyaknya inversi pada $A$, $B$, dan $C$ sama dengan $K$.
Di sini, banyaknya inversi dari suatu barisan $a$ didefinisikan sebagai banyaknya pasangan bilangan bulat $(i, j)$ yang memenuhi $1 \le i < j \le |a|$ dan $a_i > a_j$.
Masukan
Masukan diberikan dalam format berikut:
N X Y K M
- Semua nilai masukan adalah bilangan bulat.
- $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$.
Keluaran
Cetak jawabannya.
Contoh 1
3 1 1 4 998244353
24
Contoh 2
4 0 0 18 123456789
0
Contoh 3
50 10 20 1000 1000000000
805988728
Catatan
Pada contoh pertama, terdapat $24$ tripel $(A, B, C)$ yang memenuhi kondisi. Sebagai contoh, jika kita mengambil $A = (1, 2, 3)$, $B = (3, 3, 2)$, dan $C = (2, 1, 1)$, maka $(A, B, C)$ memenuhi semua kondisi.