RXD and math

Problem 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

Source

2017 Multi-University Training Contest - Team 3

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