RXD and math

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 524288/524288 K (Java/Others)

Description

RXD is a good mathematician.
One day he wants to calculate:
$$\sum_{i = 1}^{n^k}{\mu^2(i) \times \lfloor \sqrt{\frac{n^k}{i}} \rfloor}$$
output the answer module $10^9+7$.
$1\leq n, k\leq 10^{18}$
$$\mu(n) = 1 (n = 1)$$
$$\mu(n) = (-1)^k (n = p_1p_2\dots p_k)$$
$$\mu(n) = 0(otherwise)$$
$p_1,p_2,p_3\dots p_k$ are different prime numbers

Input

There are several test cases, please keep reading until EOF.
There are exact 10000 cases.
For each test case, there are 2 numbers $n, k$.

Output

For each test case, output "Case #x: y", which means the test case number and the answer.

Sample Input

10 10

Sample Output

Case #1: 999999937

Hint

liuyiding

Source

2017 Multi-University Training Contest - Te

提交代码