Сізге $N, X, Y, K$ және $M$ бүтін сандары берілген. Келесі шарттардың барлығын қанағаттандыратын ұзындығы $N$ болатын бүтін сандар тізбектерінің $(A, B, C)$ үштіктерінің санын $M$ модулі бойынша табыңыз.
- Әрбір $i = 1, 2, \dots, N$ үшін $(A_i, B_i, C_i)$ кортежі $(1, 2, 3)$ сандарының орын ауыстыруы болып табылады.
- $A$ тізбегінде дәл $X$ рет $1$ саны және $Y$ рет $2$ саны кездеседі.
- $A$, $B$ және $C$ тізбектерінің инверсиялар сандарының қосындысы $K$-ға тең.
Мұндағы $a$ тізбегінің инверсиялар саны деп $1 \le i < j \le |a|$ және $a_i > a_j$ шарттарын қанағаттандыратын $(i, j)$ бүтін сандар жұптарының саны аталады.
Кіріс деректер
Кіріс деректер келесі форматта беріледі:
N X Y K M
- Барлық кіріс мәндері бүтін сандар болып табылады.
- $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$.
Шығыс деректер
Жауапты шығарыңыз.
Мысал 1
3 1 1 4 998244353
24
Мысал 2
4 0 0 18 123456789
0
Мысал 3
50 10 20 1000 1000000000
805988728
Ескертпе
Бірінші мысалда шарттарды қанағаттандыратын $24$ үштік $(A, B, C)$ бар. Мысалы, егер $A = (1, 2, 3)$, $B = (3, 3, 2)$ және $C = (2, 1, 1)$ деп алсақ, онда $(A, B, C)$ барлық шарттарды қанағаттандырады.