Gefnar eru heiltölurnar $N, X, Y, K$ og $M$. Finnið fjölda þrennda $(A, B, C)$ af heiltalnaseríum af lengd $N$ sem uppfylla öll eftirfarandi skilyrði, modulo $M$.
- Fyrir hvert $i = 1, 2, \dots, N$ er þrenndin $(A_i, B_i, C_i)$ umröðun á $(1, 2, 3)$.
- Runan $A$ inniheldur nákvæmlega $X$ tilvik af $1$ og $Y$ tilvik af $2$.
- Summa fjölda umhverfinga í $A$, $B$ og $C$ er jöfn $K$.
Hér er fjöldi umhverfinga í runu $a$ skilgreindur sem fjöldi heiltalnapara $(i, j)$ sem uppfylla $1 \le i < j \le |a|$ og $a_i > a_j$.
Inntak
Inntakið er gefið á eftirfarandi sniði:
N X Y K M
- Öll inntaksgildi eru heiltölur.
- $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$.
Úttak
Prentið svarið.
Dæmi 1
3 1 1 4 998244353
24
Dæmi 2
4 0 0 18 123456789
0
Dæmi 3
50 10 20 1000 1000000000
805988728
Athugasemd
Í fyrsta dæminu eru $24$ þrenndir $(A, B, C)$ sem uppfylla skilyrðin. Til dæmis, ef við tökum $A = (1, 2, 3)$, $B = (3, 3, 2)$ og $C = (2, 1, 1)$, þá uppfyllir $(A, B, C)$ öll skilyrðin.