一个大小为 $n \times n$、元素填充为 $0$ 到 $m-1$ 的矩阵被称为模 $m$ 的模幻方，如果存在一个常数 $C$，使得以下同余关系成立：

$$\sum_{i=1}^{n} a_{i,j} \equiv C \pmod m \quad \text{对于 } j = 1, \dots, n$$ $$\sum_{j=1}^{n} a_{i,j} \equiv C \pmod m \quad \text{对于 } 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 \times 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$ 取模的结果。

样例

输入 1

1
3 2

输出 1

8