Problem 1411 --K-communication1411: 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
HINT
Source
[Submit][Status]