Se te dan los enteros $N, X, Y, K$ y $M$. Encuentra el número de tripletas $(A, B, C)$ de sucesiones de enteros de longitud $N$ que satisfacen todas las condiciones siguientes, módulo $M$.
- Para cada $i = 1, 2, \dots, N$, la tupla $(A_i, B_i, C_i)$ es una permutación de $(1, 2, 3)$.
- La sucesión $A$ contiene exactamente $X$ apariciones de $1$ e $Y$ apariciones de $2$.
- La suma del número de inversiones de $A$, $B$ y $C$ es igual a $K$.
Aquí, el número de inversiones de una sucesión $a$ se define como el número de pares de enteros $(i, j)$ que satisfacen $1 \le i < j \le |a|$ y $a_i > a_j$.
Entrada
La entrada se proporciona en el siguiente formato:
N X Y K M
- Todos los valores de entrada son enteros.
- $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$.
Salida
Imprime la respuesta.
Ejemplo 1
3 1 1 4 998244353
24
Ejemplo 2
4 0 0 18 123456789
0
Ejemplo 3
50 10 20 1000 1000000000
805988728
Nota
En el primer ejemplo, hay $24$ tripletas $(A, B, C)$ que satisfacen las condiciones. Por ejemplo, si tomamos $A = (1, 2, 3)$, $B = (3, 3, 2)$ y $C = (2, 1, 1)$, entonces $(A, B, C)$ satisface todas las condiciones.