#P7451. [2017年杭电多校]If the starlight never fade

    ID: 7464 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 7 上传者: 标签>CF2200提高+/省选-原根线性同余方程对称性分析欧拉函数狄利克雷卷积试除法分解质因数模逆元

[2017年杭电多校]If the starlight never fade

If the starlight never fade

Problem Description

We will give you a non-negative integer mm and a prime number pp.
And we define f(i)f\left(i\right) is the number of pair(x,y)\left(x,y\right) that satisfies (x+y)i≡xi%p\left(x + y\right) ^ {i} \equiv x ^ {i} \% p and 1≤x≤p−1,1≤y≤m1 \leq x \leq p - 1,1 \leq y \leq m. Now, you have to calculate the sum ∑i=1p−1if(i)\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+71e9+7.

Input

The first line contains only one integer TT, which indicates the number of test cases.
For each test case, there are a integer m(1≤m≤p−1)m \left(1 \leq m \leq p - 1 \right) and a prime number p(2≤p≤1e9+7)p\left(2 \leq p \leq 1e9 + 7 \right) on one line.

Output

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+71e9+7.

Sample Input

3

5 7

3 11

2 103

Sample Output

Case #1: 210

Case #2: 390

Case #3: 50388

Source

2017 Multi-University Training Contest - Team 2

https://acm.hdu.edu.cn/showproblem.php?pid=6051