14111411 SUSTech Online Judge
Problem 1411 --K-communication

1411: K-communication

Time Limit: 2 Sec  Memory Limit: 512 MB
Submit: 233  Solved: 11
[Submit][Status][Web Board]

Description

There are $$n$$ participants in some seminar, each of them is labeled from $$1$$ to $$n$$ respectively. Between each topic in the seminar, a tea break is held. To encourage communication between participants, the host asks everyone to talk to every other participant. However, not everyone is pleased, for the communication between participant $$i$$ and participant $$j$$ in the $$k$$-th tea break, the unsatisfied value is $$\gcd(i^{k}, j^{k})$$. The host wants to know what is the total unsatisfaction in each tea break.

Input

One line contains two space separated integers $$n$$ and $$k$$.
$$1 \leq n \leq 10^{11}, 1 \leq k \leq 3$$.

Output

Print the corresponding value of total unsatisfaction modulo $$1 \ 000 \ 000 \ 007$$.

Sample Input

3 2

Sample Output

3

[Submit][Status]