시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB43141229.268%

## 문제

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