Вам даны целые числа $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)$ удовлетворяет всем условиям.