You are given 2 integers $$N$$ and $$M$$. Let $$g(i)$$ denotes the number of divisors of $$i$$, that is count of positive numbers dividing $$i$$. Your task is to find the sum:
\(\sum\limits_{i=1}^{N} i^M * g(i)\)
Since the answer can be very large, you are required to print it modulo \(1000000007\) $$(10^9 + 7)$$
Input format
- The first line contains a single integer $$T$$ denoting the number of test cases.
- For each test case:
- The first and only line contains 2 space-separated integers $$N$$ and $$M$$.
Output format
For each test case, print the sum modulo \(1000000007\) $$(10^9 + 7)$$ in a separate line.
Constraints
$$ 1 \le T \le 8 \\
1 \leq N \leq 10^9 \\
0 \leq M \leq 1000 $$
In the first test case, we have $$N = 4, M = 2$$. Now, $$g(1) = 1, g(2) = 2, g(3) = 2, g(4) = 3$$. This is because:
- 1 is divisible by only 1.
- 2 is divisible by 1 and 2.
- 3 is divisible by 1 and 3.
- 4 is divisible by 1, 2 and 4.
So, \(\sum\limits_{i=1}^{4} i^M * g(i)\) = \(1*1 + 2^2*2 + 3^2*2 + 4^2*3\) = \(75\).
In the second test case, we have $$N = 1$$. So, sum is $$1$$.
