Goffi is doing his math homework and he finds an equality on his text book: \(\gcd(n - a, n) \times \gcd(n - b, n) = n^k\).
Goffi wants to know the number of (\(a, b\)) satisfy the equality, if \(n\) and \(k\) are given and \(1 \le a, b \le n\).
Note: \(\gcd(a, b)\) means greatest common divisor of \(a\) and \(b\).
输入解释
Input contains multiple test cases (less than 100). For each test case, there's one line containing two integers \(n\) and \(k\) (\(1 \le n, k \le 10^9\)).
输出解释
For each test case, output a single integer indicating the number of (\(a, b\)) modulo \(10^9+7\).
输入样例
2 1
3 2
输出样例
2
1
提示
For the first case, (2, 1) and (1, 2) satisfy the equality.