Sherlock and Permutation Sorting (Small)

Watson is curious about parallel computing. He wants to sort a permutation of the integers 1 through $N$ by breaking it into chunks, sorting each chunk on its own, and concatenating the sorted chunks.

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

Watson partitions his permutation into an ordered list of one or more chunks without changing the order of the elements, so that every element belongs to exactly one chunk and every element of a chunk is smaller than every element of any later chunk. For the permutation [2, 1, 3, 5, 4] there are exactly four legal partitions:

[[2, 1, 3], [5, 4]]
[[2, 1], [3, 5, 4]]
[[2, 1], [3], [5, 4]]
[[2, 1, 3, 5, 4]]

Watson is happiest when the number of chunks is as large as possible. Write $f(p)$ for the maximum number of chunks of a permutation $p$. For the permutation above, $f(p) = 3$.

Take every permutation $p$ of the numbers 1 through $N$ and add up $f(p)^2$. The sum can be large, so report it modulo $M$.

The first line contains the number of test cases, $T$. Each of the next $T$ lines contains two integers $N$ and $M$.

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 100$
• $1 \le N \le 100$
• $1 \le M \le 10^9$

$M$ is not always prime, and $M = 1$ is allowed.

For $N = 1$ there is a single permutation 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$ the six permutations give $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$ and $f([3, 2, 1]) = 1$, so the sum of squares is $3^2 + 2^2 + 2^2 + 1^2 + 1^2 + 1^2 = 20$.