Permutations with Given Distance#101
Butt-head has volumes of his favorite Encyclopedia for Stupid Teenagers. The volumes are numbered from to and arranged in a row. He does not like strict order, but he also dislikes complete chaos. Butt-head defines the distance of a permutation of the volumes as the sum of the absolute differences between the number and the position for all volumes.
In other words, if the permutation is (i_1, i_2, \ldots, i_n), where i_k (1 \leq k \leq n) is the number of the volume in the -th position, then its distance is
Butt-head's favorite number is , and he wants to arrange the encyclopedia volumes so that the distance is exactly . In how many ways can he do this?
The first line contains the number of tests (1 \leq T \leq 100). Each of the next lines contains two integers: the number of volumes (1 \leq n \leq 50) and the required distance (0 \leq d \leq 10000), separated by a space.
Output lines, each in the format Case #A: B, where is the test case number (starting from ), and is the number of permutations of volumes with distance , taken modulo .
Example 1