Frontier tripper, Tianjiang, has created the universe, which consists of countless worlds, one of which is called the Blue Planet. Unfortunately, the first-created world's logic is defective and thus has caused some fatal errors. After millions of years, the errors gathered together and formed the Abyss.

However, after creating the universe, the Creator Tianjiang has lost most of his power. So he was unable to fix these errors temporarily. To get the power again, He's now going on a long trip to the frontier of the universe.

The destination of the trip is a party for creators of all universes. They holds regular competitions, which is named International Casually Playing Competition, or famous as ICPC. The top 210 competitors would gained strong power. Competitors are firstly ranked by the number of games they played successfully, if same, then they'd be ranked by the total used time. In the last 46th ICPC on April 17, Tianjiang was knocked out because he was 26 seconds behind and only played 2 games. He got the time used time of 4:44:37 while the 210th competitor got 4:44:11.

Since he failed last time lacking of math thinking. He'd like train himself with lots of math problems. And here's one easy math problem:

For an integer n , define \varphi(n) as the number of positive integers from [1,n] that co-prime with n , and define \sigma(n) as the sum of all the positive divisors of n .

Given n,k , you need to calculate \sum_{i=1}^n\varphi(i^k)\cdot\sigma(i^k) modulus 10^9+7 .

Input two integers n,k(1\le n,k\le10^6) .

Output one integer (\sum_{i=1}^n\varphi(i^k)\cdot\sigma(i^k))\bmod(10^9+7) .

For example, if n=6 , then \varphi(6)=2 because two numbers 1,5 are co-prime with 6 , and \sigma(6)=12 because all the positive divisors are 1,2,3,6 and 1+2+3+6=12 .