Problem H: K-communication

Problem H: K-communication

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


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.


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


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

Sample Input

3 2

Sample Output