셜록과 순열 정렬 (Small)

왓슨은 병렬 계산에 관심이 많다. 그래서 1부터 $N$까지의 정수로 이루어진 순열을 여러 덩어리로 쪼갠 다음, 각 덩어리를 따로 정렬하고 다시 이어 붙이는 방식으로 정렬하려고 한다.

순열 $p_1, p_2, \ldots, p_N$에서 덩어리는 연속한 부분 배열이다. 즉 $1 \le i \le j \le N$인 인덱스 $i$와 $j$에 대해 원소 $p_i, p_{i+1}, \ldots, p_j$를 뜻한다.

왓슨은 원소의 순서를 그대로 둔 채 순열을 하나 이상의 덩어리로 이루어진 순서 있는 목록으로 나눈다. 이때 모든 원소는 정확히 한 덩어리에 속하고, 한 덩어리의 모든 원소는 그 뒤에 오는 모든 덩어리의 모든 원소보다 작아야 한다. 예를 들어 순열 [2, 1, 3, 5, 4]를 나누는 방법은 다음 네 가지뿐이다.

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

왓슨은 덩어리가 많을수록 기뻐한다. 순열 $p$에서 만들 수 있는 덩어리의 최대 개수를 $f(p)$라고 쓴다. 위 순열에서는 $f(p) = 3$이다.

1부터 $N$까지의 수로 만드는 모든 순열 $p$에 대해 $f(p)^2$의 합을 구하라. 합이 매우 커질 수 있으므로 $M$으로 나눈 나머지를 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개의 줄에 각각 두 정수 $N$과 $M$이 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 크기가 $N$인 모든 순열 $p$에 대한 $f(p)^2$의 합을 $M$으로 나눈 나머지이다.

• $1 \le T \le 100$
• $1 \le N \le 100$
• $1 \le M \le 10^9$

$M$이 소수라는 보장은 없고, $M = 1$도 주어질 수 있다.

$N = 1$이면 순열이 하나뿐이고 $f([1]) = 1$이므로 제곱의 합은 1이다.

$N = 2$이면 순열이 둘이고 $f([1, 2]) = 2$, $f([2, 1]) = 1$이므로 제곱의 합은 $2^2 + 1^2 = 5$이다.

$N = 3$이면 여섯 순열에서 $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$이므로 제곱의 합은 $3^2 + 2^2 + 2^2 + 1^2 + 1^2 + 1^2 = 20$이다.