Problem Description

The least common multiple (LCM) of two positive integers $a$ and $b$ is the smallest positive integer that is a multiple of both $a$ and $b$.

Given two positive integers $N$ and $K$, find the sum of $LCM(i, K)$ for all integers $i$ from 1 to $N$, and output the result modulo $1,000,000,007$.

Input Format

The input is given from the standard input in the following format:

$N$ $K$

• The first line contains two integers $N$ and $K$ ($1 ≦ N, K ≦ 10^9$) separated by a space.

Output Format

Output the sum modulo $1,000,000,007$ to the standard output.

Do not forget the newline at the end of the output.

Sample Input and Output

Sample Input #1

4 2

Sample Output #1

14

Sample Input #2

10000 100

Sample Output #2

865504986

Sample Input #3

1000000000 90

Sample Output #3

50001213

Sample Input #4

1000000000 999999900

Sample Output #4

231285006

Notes/Hints

Partial Points

This problem is very difficult for an AtCoder Beginner Contest problem, so it is worth 101 points in total, with partial points available.

• 5 points for test cases where $1 ≦ N, K ≦ 100$.
• Another 10 points for test cases where $1 ≦ N ≦ 10^4$ and $1 ≦ K ≦ 100$.
• Another 85 points for test cases where $1 ≦ N ≦ 10^9$ and $1 ≦ K ≦ 100$. This totals 100 points.

Sample Explanation 1

$LCM(1, 2) + LCM(2, 2) + LCM(3, 2) + LCM(4, 2) = 2 + 2 + 6 + 4 = 14$.

见题面 Input 部分

见题面 Output 部分