Gegeben sind ganze Zahlen $N, X, Y, K$ und $M$. Bestimme die Anzahl der Tripel $(A, B, C)$ von ganzzahligen Folgen der Länge $N$, die alle folgenden Bedingungen erfüllen, modulo $M$.
- Für jedes $i = 1, 2, \dots, N$ ist das Tupel $(A_i, B_i, C_i)$ eine Permutation von $(1, 2, 3)$.
- Die Folge $A$ enthält genau $X$ Vorkommen von $1$ und $Y$ Vorkommen von $2$.
- Die Summe der Anzahlen der Inversionen von $A$, $B$ und $C$ ist gleich $K$.
Hierbei ist die Anzahl der Inversionen einer Folge $a$ definiert als die Anzahl der Paare ganzer Zahlen $(i, j)$, die $1 \le i < j \le |a|$ und $a_i > a_j$ erfüllen.
Eingabe
Die Eingabe erfolgt im folgenden Format:
N X Y K M
- Alle Eingabewerte sind ganze Zahlen.
- $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$.
Ausgabe
Gib die Antwort aus.
Beispiel 1
3 1 1 4 998244353
24
Beispiel 2
4 0 0 18 123456789
0
Beispiel 3
50 10 20 1000 1000000000
805988728
Hinweis
Im ersten Beispiel gibt es $24$ Tripel $(A, B, C)$, die die Bedingungen erfüllen. Wenn wir beispielsweise $A = (1, 2, 3)$, $B = (3, 3, 2)$ und $C = (2, 1, 1)$ wählen, erfüllt $(A, B, C)$ alle Bedingungen.