Sinulle annetaan kokonaisluvut $N, X, Y, K$ ja $M$. Etsi sellaisten pituutta $N$ olevien kokonaislukujonojen kolmikoiden $(A, B, C)$ lukumäärä modulo $M$, jotka täyttävät kaikki seuraavat ehdot.
- Jokaisella $i = 1, 2, \dots, N$ kolmikko $(A_i, B_i, C_i)$ on lukujen $(1, 2, 3)$ permutaatio.
- Jono $A$ sisältää täsmälleen $X$ kappaletta lukua $1$ ja $Y$ kappaletta lukua $2$.
- Jonojen $A$, $B$ ja $C$ inversioiden lukumäärien summa on $K$.
Tässä jonon $a$ inversioiden lukumäärä määritellään sellaisten kokonaislukuparien $(i, j)$ lukumääräksi, joille pätee $1 \le i < j \le |a|$ ja $a_i > a_j$.
Syöte
Syöte annetaan seuraavassa muodossa:
N X Y K M
- Kaikki syötteen arvot ovat kokonaislukuja.
- $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$.
Tuloste
Tulosta vastaus.
Esimerkki 1
3 1 1 4 998244353
24
Esimerkki 2
4 0 0 18 123456789
0
Esimerkki 3
50 10 20 1000 1000000000
805988728
Huomautus
Ensimmäisessä esimerkissä on $24$ kolmikkoa $(A, B, C)$, jotka täyttävät ehdot. Esimerkiksi jos valitsemme $A = (1, 2, 3)$, $B = (3, 3, 2)$ ja $C = (2, 1, 1)$, niin $(A, B, C)$ täyttää kaikki ehdot.