Problem H: K-communication ## Problem H: 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

[Submit][Status]