题目描述

题目译自 PA 2025 Runda 5 Gładkie permutacje

一个序列 $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)$-平滑的，如果它同时满足：

1. 最长递增子序列长度为 $a$；
2. 最长递减子序列长度为 $b$；
3. 最长单峰子序列长度为 $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)$-平滑排列的集合非空且有限。请你写一个程序，计算：

1. 最长的 $(a, b, c)$-平滑排列的长度（记为 $n$）；
2. 长度为 $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$ 取模的值。

样例 1

输入：$2 2 3 10000019$ 输出：$4 4$

所有 $(2,2,3)$-平滑排列的集合如下： $1,3,2$；$2,3,1$；$2,1,4,3$；$2,4,1,3$；$3,1,4,2$；$3,4,1,2$ 其中 4 个最长的排列长度为 $4$。

样例 2

输入：$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}$

样例 3

输入：$8 9 11 15872567$ 输出：$57 57$

数据范围与提示

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