Ti vengono dati gli interi $N, X, Y, K$ e $M$. Trova il numero di terne $(A, B, C)$ di sequenze di interi di lunghezza $N$ che soddisfano tutte le seguenti condizioni, modulo $M$.
- Per ogni $i = 1, 2, \dots, N$, la terna $(A_i, B_i, C_i)$ è una permutazione di $(1, 2, 3)$.
- La sequenza $A$ contiene esattamente $X$ occorrenze di $1$ e $Y$ occorrenze di $2$.
- La somma del numero di inversioni di $A$, $B$ e $C$ è uguale a $K$.
Qui, il numero di inversioni di una sequenza $a$ è definito come il numero di coppie di interi $(i, j)$ che soddisfano $1 \le i < j \le |a|$ e $a_i > a_j$.
Input
L'input è fornito nel seguente formato:
N X Y K M
- Tutti i valori in input sono interi.
- $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$.
Output
Stampa la risposta.
Esempio 1
3 1 1 4 998244353
24
Esempio 2
4 0 0 18 123456789
0
Esempio 3
50 10 20 1000 1000000000
805988728
Nota
Nel primo esempio, ci sono $24$ terne $(A, B, C)$ che soddisfano le condizioni. Ad esempio, se prendiamo $A = (1, 2, 3)$, $B = (3, 3, 2)$ e $C = (2, 1, 1)$, allora $(A, B, C)$ soddisfa tutte le condizioni.