Modulo-magic squares

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\).