모듈로 마방진

(0)부터 (m-1)까지의 정수로 채워진 (n \times n) 행렬이 다음 합동식이 성립하는 상수 (C)를 가질 때, 이 행렬을 법 (m)에 대한 모듈로 마방진이라고 한다:

[\sum_{i=1}^{n}{a_{i,j}} \equiv C \pmod{m} \quad \text{for } j = 1, \dots, n] [\sum_{j=1}^{n}{a_{i,j}} \equiv C \pmod{m} \quad \text{for } i = 1, \dots, n] [\sum_{i=1}^{n}{a_{i,i}} \equiv C \pmod{m}] [\sum_{i=1}^{n}{a_{i,n-i+1}} \equiv C \pmod{m}]

즉, 각 행, 열 및 두 대각선에 있는 수들의 합을 (m)으로 나눈 나머지가 모두 같다.

(n)과 (m)이 주어졌을 때, 크기가 (n)인 법 (m)에 대한 서로 다른 모듈로 마방진이 몇 개 존재하는지 구하시오.

입력의 첫 줄에는 정수 (T)가 주어진다: 테스트 케이스의 수 ((1 \le T \le 100)). 이후 (T)개의 줄이 이어진다. 각 줄에는 두 정수 (n)과 (m)이 주어진다: 행렬의 크기와 법 ((3 \le n \le 10^9, 2 \le m \le 10^9)).

각 테스트 케이스에 대해 모듈로 마방진의 개수를 한 줄에 하나씩 출력한다. 답이 매우 클 수 있으므로 (10^9 + 7)로 나눈 나머지를 출력한다.