Вам дано цілі числа $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)$ задовольняє всі умови.