题目背景

PA 2025 R5A.

题目描述

对于序列 $a=[a_1,a_2,\ldots,a_k]$，我们说：

• $a$ 是递增的，当且仅当 $a_1\lt a_2\lt \ldots\lt a_k$；
• $a$ 是递减的，当且仅当 $a_1\gt a_2\gt \ldots\gt a_k$；
• $a$ 是单峰的，当且仅当存在 $1\le l\le k$，使得 $[a_1,a_2,\ldots,a_l]$ 是递增的，且 $[a_l,a_{l+1},\ldots,a_k]$ 是递减的。

特别地，若 $k=1$，则 $a$ 既是递增的，也是递减的，也是单峰的。

对于正整数 $a,b,c$，我们说一个排列 $p$ 是好的，当且仅当：

• $p$ 的最长上升子序列（LIS）长度为 $a$；
• $p$ 的最长下降子序列（LDS）长度为 $b$；
• $p$ 的最长单峰子序列长度为 $c$。

例

$a=2,b=3,c=4$ 时，排列 $[4, 5, 2, 3, 1]$ 是好的，因为：

• LIS 为 $[4, 5]$（长度 $2$）；
• LDS为 $[4, 2, 1]$（长度 $3$）；
• 最长单峰子序列为 $[4, 5, 3, 1]$（长度 $4$）。

给定 $a,b,c$ 满足 $1\le a\le b\le c\lt a+b$。求出：

1. 好的排列 $p$ 的长度的最大值（记为 $n$）；
2. 长度为 $n$ 的好的排列的数量对大素数 $\mathrm{mod}$ 取模后的结果。

可以证明，在题目条件下，好的排列至少有一个，且只有有限个。

输入格式

一行四个正整数 $a,b,c,\mathrm{mod}$。

输出格式

一行两个正整数：

• 最长的好的排列的长度 $n$；
• 长度为 $n$ 的好的排列的数量对 $\mathrm{mod}$ 取模后的结果。

2 2 3 10000019

4 4

2 3 3 999999937

5 10

8 9 11 15872567

57 57

提示

样例解释

• 样例 $1$ 解释：

样例 $1$ 中，$a=2,b=2,c=3$。

所有好的排列为：

• $[1, 3, 2]$；
• $[2, 3, 1]$；
• $[2, 1, 4, 3]$；
• $[2, 4, 1, 3]$；
• $[3, 1, 4, 2]$；
• $[3, 4, 1, 2]$。

其中最长的排列长度为 $4$。

• 样例 $2$ 解释：

样例 $2$ 中，$a=2,b=3,c=3$。

所有好的排列为：

• $[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]$。

子任务

在大于 $0$ 分的子任务中，保证 $c = a + b - 1$。

数据范围

• $1 \leq a \leq 20$；
• $a \leq b \leq 5\times 10^4$；
• $b \leq c \lt a + b$；
• $10^7 \leq \mathrm{mod} \leq 10^9$；
• $\mathrm{mod}$ 是素数。