P16583 [GKS 2016 #B] Sherlock and Permutation Sorting

Sherlock 和 Watson 已经在他们的计算机编程课程中接触过排序。Watson 一直对并行计算很好奇，他想通过将排列分块、分别对每个块排序，然后再拼接起来的方式，对一个由 $1$ 到 $N$ 的整数构成的排列进行排序。 对于一个排列 $p_1, p_2, \dots, p_N$，一个**块**是指该排列中一段连续的子数组：即对于满足 $1 \leq i \leq j \leq N$ 的下标 $i$ 和 $j$，元素序列 $p_i, p_{i+1}, \dots, p_j$。 Watson 想将他的排列划分为一个由若干块组成的有序列表（不改变元素原有的顺序），使得排列中的每个元素恰好属于一个块，并且任意一个块中的所有元素都小于任意一个位于它后面的块中的所有元素。例如，对于排列 $[2, 1, 3, 5, 4]$，只有以下四种合法的划分方式：$[[2, 1, 3], [5, 4]]$、$[[2, 1], [3, 5, 4]]$、$[[2, 1], [3], [5, 4]]$ 或 $[[2, 1, 3, 5, 4]]$。当块的数量尽可能多时 Watson 最为高兴；我们将排列 $p$ 的最大块数记为 $f(p)$。在这个例子中，最大块数为 $3$。 Watson 想要考虑所有由 $1$ 到 $N$ 构成的排列 $p$，并计算 $f(p)$ 的平方和。Watson 知道 Sherlock 可能会派上用场，于是向他求助，但 Sherlock 也一样毫无头绪，所以来请你帮忙。由于平方和可能很大，请输出它对 $M$ 取模的结果。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由一行两个整数 $N$ 和 $M$ 组成。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是所有大小为 $N$ 的排列 $p$ 的 $f(p)$ 的平方和模 $M$ 的结果。

在样例 $1$ 中，只有一个排列。$f([1]) \times f([1]) \bmod 2 = 1$。 在样例 $2$ 中，有两个排列。 $f([1, 2]) = 2$。 $f([2, 1]) = 1$。 $(2^2 + 1^2) \bmod 4 = 1$。 在样例 $3$ 中，有六个排列。 $f([1, 2, 3]) = 3$。 $f([1, 3, 2]) = 2$。 $f([2, 1, 3]) = 2$。 $f([2, 3, 1]) = 1$。 $f([3, 1, 2]) = 1$。 $f([3, 2, 1]) = 1$。 $(3^2 + 2^2 + 2^2 + 1^2 + 1^2 + 1^2) \bmod 7 = 6$。 ### 限制条件 $1 \le M \le 10^9$。 **小数据集（测试集 1 – 可见）** $1 \le T \le 100$。 $1 \le N \le 100$。 **大数据集（测试集 2 – 隐藏）** $1 \le T \le 20$。 $1 \le N \le 5000$。 翻译由 DeepSeek V4 Pro 完成