Xiao A and Xiao C are playing a game. In each round, Xiao A chooses an integer $i$ from $1$ to $n$, and then Xiao C chooses an integer $x$ from $1$ to $i$. This generates a value of $\gcd(i, x)$. As is well known, Xiao C is a repeater; he repeats this operation $k$ times. The total value of the game is the least common multiple (LCM) of the values generated by Xiao C in each of the $k$ rounds.

Now, Xiao A wants to know the sum of the total game values over all possible scenarios. For obvious reasons, you only need to output the sum modulo $10^9+7$.

Input

A single line containing two positive integers $n$ and $k$.

Output

A single integer representing the sum of the game values.

Examples

Input 1

3 1

Output 1

9

Note 1

For Sample Input 1, the value is: $\gcd(1,1)+\gcd(2,1)+\gcd(2,2)+\gcd(3,1)+\gcd(3,2)+\gcd(3,3)=9$

Input 2

5 2

Output 2

130

Input 3

1000000 1000

Output 3

763267594

Constraints

$1 \le n \le 10^9, 1 \le k \le 10^9, 1 \le n*k \le 10^9$

This problem is evaluated using subtasks (empty cells indicate no special properties).