We will give you a non-negative integer $m$ and a prime number $p$. And we define $f\left(i\right)$ is the number of pair$\left(x,y\right)$ that satisfies $\left(x + y\right) ^ {i} \equiv x ^ {i} \% p$ and $1 \leq x \leq p - 1,1 \leq y \leq m$. Now, you have to calculate the sum $\sum_{i=1}^{p-1}if\left(i\right)$. Maybe the sum is too big,so you only need to output the sum after mod $1e9+7$.
输入解释
The first line contains only one integer $T$, which indicates the number of test cases. For each test case, there are a integer $m \left(1 \leq m \leq p - 1 \right)$ and a prime number $p\left(2 \leq p \leq 1e9 + 7 \right)$ on one line.
输出解释
For each test case, output one line "Case #x: y", where x is the case number (starting from 1) and y is the sum after mod $1e9+7$.