시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 19 8 6 35.294%

## 문제

A matrix of size $n \times n$ filled with integers from $0$ to $m − 1$ is called a modulo-magic square modulo $m$ if there exists a constant $C$ such that the following congruence relations hold:

$\sum_{i=1}^{n}{a_{i,j}} \equiv C ~~~~~(\text{mod } m)~~~~~ \text{for } j = 1, \dots, n \\ \sum_{j=1}^{n}{a_{i,j}} \equiv C ~~~~~(\text{mod } m)~~~~~ \text{for } i = 1, \dots, n \\ \sum_{i=1}^{n}{a_{i,i}} \equiv C ~~~~~(\text{mod } m) \\ \sum_{i=1}^{n}{a_{i,n-i+1}} \equiv C ~~~~~(\text{mod } m)$

In words, the sums of numbers in each row, column and both diagonals modulo $m$ are equal.

Given $n$ and $m$, find how many different modulo-magic squares modulo $m$ of size $n$ exist.

## 입력

The first line of input contains an integer $T$: the number of test cases ($1 \le T \le 100$). After that, $T$ lines follow. Each of these lines contains two integers $n$ and $m$: the size of the matrix and the modulo ($3 \le n \le 10^9,2 \le m \le 10^9$).

## 출력

For each test case, output the number of modulo-magic squares on a separate line. Since the answers can be very large, output them modulo $10^9 + 7$.

## 예제 입력 1

1
3 2


## 예제 출력 1

8