P17394 [ICPC 2018 Shenyang R] Insertion Sort

插入排序是一种简单的排序算法，每次迭代构建一个最终有序的数组，一次添加一个元素。 更准确地说，插入排序重复执行以下过程：每次取出一个输入元素，扩大已排序的输出列表。在每次迭代中，插入排序从输入数据中移除一个元素，在已排序列表中查找它应该插入的位置，并将其插入该位置。重复这一过程直到没有输入元素剩余。 这种排序通常采用就地方式进行，即沿着数组向后迭代，在身后扩展已排序的数组。在每个数组位置上，它会检查该位置的值与已排序数组中的最大值（恰好位于刚刚检查过的前一个数组位置上）的大小关系。若更大，则将元素保留在原位，并移动到下一个位置。若更小，则在已排序数组中寻找正确的位置，将所有更大的值向上移动以腾出空位，并将其插入此正确位置。 经过 $k$ 次迭代后得到的数组具有前 $k$ 个元素已排序的性质。每次迭代中，输入的第一个剩余元素被取出，并在结果中的正确位置插入，从而扩展结果。 Knuth 是一位 ACM-ICPC 大师，为你提供了一份插入排序的修改版伪代码实现。对于可排序元素组成的数组 $A$（下标从 $1$ 开始），他修改后的算法可以表述如下： :::align{center}  ::: 给定参数 $k$，要求你统计 $1$ 到 $n$ 的所有不同排列中，经过他的修改版插入排序后，每个排列都会变成一个 **几乎有序的排列** 的排列数量。他指出，一个 $1$ 到 $n$ 的排列，如果其最长上升子序列的长度至少为 $(n - 1)$，则该排列是几乎有序的。

输入包含多组测试数据，第一行包含一个正整数 $T$，表示测试数据的组数，最多为 $5000$。 对于每组测试数据，唯一的一行包含三个整数 $n, k$ 和 $q$，分别表示排列的长度、他实现中的参数以及输出所需的质数，满足 $1 \leq n, k \leq 50$，$10^8 \leq q \leq 10^9$。

对于每组测试数据，输出一行包含 “Case #x: y”（不含引号），其中 $x$ 是测试数据编号（从 $1$ 开始），$y$ 是满足要求的排列数量除以 $q$ 的余数。

在第一个样例中，我们可以发现 $10$ 个满足条件的排列，列举如下： * $[1, 2, 3, 4]$； * $[1, 2, 4, 3]$； * $[1, 3, 2, 4]$； * $[1, 3, 4, 2]$； * $[1, 4, 2, 3]$； * $[2, 1, 3, 4]$； * $[2, 3, 1, 4]$； * $[2, 3, 4, 1]$； * $[3, 1, 2, 4]$； * $[4, 1, 2, 3]$。 翻译由 DeepSeek V4 Pro 完成