406047: GYM102222 I Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Izdihar is an ACM-ICPC master and provides a pseudocode implementation about the bubble sort for you. The algorithm for a list of sortable items A can be expressed as (1-based array):

1. n = length(A)
2. repeat
   1. swapped = false
   2. for i = 2 to n inclusive do
      1. if A[i-1] > A[i] then
         1. swap( A[i-1], A[i] )
         2. swapped = true
         end if
      end for
   until not swapped

She says a permutation of $$$1$$$ to $$$n$$$ is almost sorted if the length of its longest increasing subsequence is at least $$$n-1$$$.

You are asked to count the number of permutations of $$$1$$$ to $$$n$$$ which, after $$$k$$$ times passing through the list in the bubble sort, would become an almost sorted permutation.

The input contains several test cases, and the first line is a positive $$$T$$$ indicating the number of test cases which is up to $$$5000$$$.

For each test case, a line contains three integers $$$n$$$, $$$k~(1 \leq n, k \leq 50)$$$ which are described as above, and $$$q~(10^8 \leq q \leq 10^9)$$$ which is a prime number for the output.

For each test case, output a line containing Case #x: y, where x is the test case number starting from $$$1$$$. And y is the remainder of the number of permutations which meet the requirement, dividing by $$$q$$$.

5
5 1 998244353
5 2 998244353
5 3 998244353
5 4 998244353
5 5 998244353

Case #1: 74
Case #2: 114
Case #3: 120
Case #4: 120
Case #5: 120