셜록과 순열 정렬 (라지)

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

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

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

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

왓슨은 덩어리가 많을수록 기뻐한다. 순열 $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 20$
• $1 \le N \le 5000$
• $1 \le M \le 10^9$

$N = 1$이면 순열은 $[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$이다.

$M$이 $1$이면 나머지는 항상 $0$이다.