On vous donne les entiers $N, X, Y, K$ et $M$. Trouvez le nombre de triplets $(A, B, C)$ de suites d'entiers de longueur $N$ qui vérifient toutes les conditions suivantes, modulo $M$.
- Pour chaque $i = 1, 2, \dots, N$, le triplet $(A_i, B_i, C_i)$ est une permutation de $(1, 2, 3)$.
- La suite $A$ contient exactement $X$ occurrences de $1$ et $Y$ occurrences de $2$.
- La somme des nombres d'inversions de $A$, $B$ et $C$ est égale à $K$.
Ici, le nombre d'inversions d'une suite $a$ est défini comme le nombre de couples d'entiers $(i, j)$ vérifiant $1 \le i < j \le |a|$ et $a_i > a_j$.
Entrée
L'entrée est donnée dans le format suivant :
N X Y K M
- Toutes les valeurs d'entrée sont des entiers.
- $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$.
Sortie
Affichez la réponse.
Exemple 1
3 1 1 4 998244353
24
Exemple 2
4 0 0 18 123456789
0
Exemple 3
50 10 20 1000 1000000000
805988728
Note
Dans le premier exemple, il y a $24$ triplets $(A, B, C)$ qui vérifient les conditions. Par exemple, si l'on prend $A = (1, 2, 3)$, $B = (3, 3, 2)$ et $C = (2, 1, 1)$, alors $(A, B, C)$ vérifie toutes les conditions.