Последовательность $p_1, p_2, \dots, p_k$ называется: возрастающей, если $p_1 < p_2 < \dots < p_k$; убывающей, если $p_1 > p_2 > \dots > p_k$; * выпуклой, если для некоторого $1 \le l \le k$ последовательность $p_1, p_2, \dots, p_l$ является возрастающей, а последовательность $p_l, p_{l+1}, \dots, p_k$ является убывающей.
В частности, последовательность из одного элемента считается одновременно возрастающей, убывающей и выпуклой.
Перестановка называется $(a, b, c)$-гладкой, если одновременно выполняются три условия: её самая длинная возрастающая подпоследовательность имеет длину $a$, её самая длинная убывающая подпоследовательность имеет длину $b$, * её самая длинная выпуклая подпоследовательность имеет длину $c$.
Например, перестановка $4, 5, 2, 3, 1$ является $(2, 3, 4)$-гладкой, так как: её самая длинная возрастающая подпоследовательность — это, например, $4, 5$; её самая длинная убывающая подпоследовательность — это, например, $4, 2, 1$; * её самая длинная выпуклая подпоследовательность — это, например, $4, 5, 3, 1$.
Даны три целых числа $a, b, c$, удовлетворяющие условиям $1 \le a \le b \le c < a + b$, и простое число $p$. Можно доказать, что для такой тройки $a, b, c$ множество всех $(a, b, c)$-гладких перестановок непусто и конечно.
Напишите программу, которая определит: длину самой длинной $(a, b, c)$-гладкой перестановки (обозначим её через $n$), остаток от деления на $p$ количества $(a, b, c)$-гладких перестановок длины $n$.
Входные данные
В единственной строке входных данных содержатся четыре целых числа $a, b, c, p$ ($1 \le a \le 20$, $a \le b \le 50\,000$, $b \le c < a + b$, $10^7 \le p \le 10^9$), обозначающие соответственно: максимальные длины возрастающих, убывающих и выпуклых подпоследовательностей в рассматриваемых перестановках, а также простое число $p$.
Выходные данные
В единственной строке выходных данных должны быть выведены два целых числа: длина самой длинной $(a, b, c)$-гладкой перестановки и количество $(a, b, c)$-гладких перестановок такой длины по модулю $p$.
Примеры
Пример 1
2 2 3 10000019
4 4
Пример 2
2 3 3 999999937
5 10
Пример 3
8 9 11 15872567
57 57
Примечание
Множество всех $(2, 2, 3)$-гладких перестановок следующее: $1, 3, 2 \quad 2, 3, 1 \quad 2, 1, 4, 3 \quad 2, 4, 1, 3 \quad 3, 1, 4, 2 \quad 3, 4, 1, 2$ Самые длинные 4 из них имеют длину 4.
Во втором примере рассматриваются $(2, 3, 3)$-гладкие перестановки длины 5: $3, 2, 1, 5, 4 \quad 3, 2, 5, 1, 4 \quad 4, 2, 1, 5, 3 \quad 4, 2, 5, 1, 3 \quad 4, 3, 1, 5, 2$ $4, 3, 5, 1, 2 \quad 5, 2, 1, 4, 3 \quad 5, 2, 4, 1, 3 \quad 5, 3, 1, 4, 2 \quad 5, 3, 4, 1, 2$
Подзадачи
В тестах, оцениваемых в некоторое ненулевое количество баллов, выполняется условие $c = a + b - 1$.