시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 116 | 21 | 19 | 17.117% |
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 3 2
8