Define function f(n) as the sum of all factors of n, for example f(1) = 1,f(5) = 1 + 5 = 6,f(6) = 1 + 2 + 3 + 6 = 12.

Given n and k, you need to calculate

\sum_{i=1}^n f(i^k)

Since the answer is too large, you need to output the remainder of the answer divided by 10^9+ 7.

One line, two numbers n and k, (1≤n, k≤10^7)

One line indicates the answer.

f(1^2) +f(2^2) = (1) + (1 + 2 + 4) = 8