题目描述

一个序列 $p_{1}, p_{2}, \ldots, p_{k}$ 可以定义为：

• 递增，如果 $p_{1} < p_{2} < \ldots < p_{k}$；
• 递减，如果 $p_{1} > p_{2} > \ldots > p_{k}$；
• 凸形，如果存在某个 $1 \leq l \leq k$，使得 $p_{1}, p_{2}, \ldots, p_{l}$ 递增，而 $p_{l}, p_{l+1}, \ldots, 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 \leq a \leq b \leq c < a+b$）和一个质数 $p$。可以证明，对于这样的 $a, b, c$，$(a, b, c)$-平滑排列的集合非空且有限。请你写一个程序，计算：

• 最长的 $(a, b, c)$-平滑排列的长度（记为 $n$）；
• 长度为 $n$ 的 $(a, b, c)$-平滑排列数量对 $p$ 取模的结果。

输入格式

输入只有一行，包含四个整数 $a, b, c, p$ $(1 \leq a \leq 20, a \leq b \leq 50000, b \leq c < a+b, 10^{7} \leq p \leq 10^{9})$，分别表示递增、递减、凸形子序列的最大长度，以及质数 $p$。

输出格式

输出一行，包含两个整数：最长的 $(a, b, c)$-平滑排列的长度，以及该长度的 $(a, b, c)$-平滑排列数量对 $p$ 取模的值。

2 2 3 10000019

4 4

所有 $(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 999999937

5 10

在第二个样例中，考虑长度为 $5$ 的 $(2,3,3)$-平滑排列：

$$\begin{array}{lllll} 3,2,1,5,4 & 3,2,5,1,4 & 4,2,1,5,3 & 4,2,5,1,3 & 4,3,1,5,2 \\ 4,3,5,1,2 & 5,2,1,4,3 & 5,2,4,1,3 & 5,3,1,4,2 & 5,3,4,1,2 \end{array} $$

8 9 11 15872567

57 57

数据范围与提示

对于某些子任务，满足 $c = a + b - 1$。