أُعطيتَ الأعداد الصحيحة $N, X, Y, K$ و $M$. أوجد عدد الثلاثيات $(A, B, C)$ من متتاليات الأعداد الصحيحة التي طولها $N$ والتي تحقق جميع الشروط التالية، بباقي القسمة على $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$ بأنه عدد أزواج الأعداد الصحيحة $(i, j)$ التي تحقق $1 \le i < j \le |a|$ و $a_i > a_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)$ تحقق جميع الشروط.