셜록과 순열 정렬

셜록과 왓슨은 컴퓨터 프로그래밍 수업에서 이미 정렬을 배웠다. 왓슨은 늘 병렬 컴퓨팅에 관심이 많았으며, 정수 1부터 N까지의 순열을 여러 청크로 나누고, 각 청크를 개별적으로 정렬한 다음, 이들을 이어 붙이는 방식으로 정렬하려 한다.

순열 p_{1}, p_{2}, ..., p_{N}에서 청크란 순열의 연속 부분 배열이다. 즉, 인덱스 i와 j에 있는 원소들에 대해 1 ≤ i ≤ j ≤ N을 만족하는 원소들의 수열 p_{i}, p_{i + 1}, ..., 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)로 나타낸다. 이 예제에서 청크 수의 최댓값은 3이다.

왓슨은 수 1부터 N까지로 이루어진 모든 순열 p를 고려하여 f(p)의 제곱의 합을 구하려 한다. 왓슨은 셜록이 도움이 될지도 모른다고 생각해 그에게 도움을 청하지만, 셜록도 왓슨만큼이나 아무것도 몰라 여러분에게 도움을 청한다. 제곱의 합은 클 수 있으므로, 이를 M으로 나눈 나머지를 구한다.

제한

메모리 제한: 1GB.

1 ≤ M ≤ $10^{9}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ T ≤ 100. 시간 제한: 20초. 1 ≤ N ≤ 100.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ T ≤ 20. 시간 제한: 60초. 1 ≤ N ≤ 5000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 N과 M이 있는 한 줄로 이루어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 크기가 N인 모든 순열 p에 대한 f(p)의 제곱의 합을 M으로 나눈 나머지이다.

케이스 1에는 순열이 하나뿐이다. f([1]) * f([1]) % 2 = 1.

케이스 2에는 순열이 두 개 있다. f([1, 2]) = 2. f([2, 1]) = 1. (2^{2} + 1^{2}) % 4 = 1.

케이스 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}) % 7 = 6.