Sherlock and Permutation Sorting (Large)

Sherlock and Watson learned sorting in their programming course. Watson is curious about parallel computing, so he wants to sort a permutation of the integers $1$ through $N$ by splitting it into chunks, sorting each chunk on its own, and then concatenating them.

For a permutation $p_1, p_2, \dots, p_N$, a chunk is a contiguous subarray: the elements $p_i, p_{i+1}, \dots, p_j$ for indices $i$ and $j$ with $1 \le i \le j \le N$.

Watson partitions the permutation into an ordered list of one or more chunks without changing the order of the elements. Every element belongs to exactly one chunk, and every element of a chunk is smaller than every element of every later chunk. For example, for the permutation $[2, 1, 3, 5, 4]$ these are the only four legal partitions.

$[[2, 1, 3], [5, 4]] \quad [[2, 1], [3, 5, 4]] \quad [[2, 1], [3], [5, 4]] \quad [[2, 1, 3, 5, 4]]$

Watson is happiest when there are as many chunks as possible. Write $f(p)$ for the maximum number of chunks of a permutation $p$. In the example above that maximum is $3$.

Compute the sum of $f(p)^2$ over all permutations $p$ of the numbers $1$ through $N$. The sum can be large, so print it modulo $M$.

The first line contains the number of test cases, $T$. $T$ test cases follow. Each test case is one line with two integers $N$ and $M$ separated by a space.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from $1$ and $y$ is the sum of $f(p)^2$ over all permutations $p$ of size $N$, modulo $M$.

• $1 \le T \le 20$
• $1 \le N \le 5000$
• $1 \le M \le 10^9$

For $N = 1$ the only permutation is $[1]$ and $f([1]) = 1$, so the sum of squares is $1$.

For $N = 2$ there are two permutations. $f([1, 2]) = 2$ and $f([2, 1]) = 1$, so the sum of squares is $2^2 + 1^2 = 5$.

For $N = 3$ there are six permutations. $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$, so the sum of squares is $3^2 + 2^2 + 2^2 + 1^2 + 1^2 + 1^2 = 20$.

If $M$ is $1$, the remainder is always $0$.