問題文

$2$ つの正整数 $a,$ $b$ の最小公倍数 $LCM(a, b)$ とは、 $a$ の倍数であり、かつ $b$ の倍数でもあるような正整数のうち最小のものをいいます。

$2$ つの正整数 $N,$ $K$ が与えられます。 $1$ 以上 $N$ 以下のすべての整数 $i$ について $LCM(i, K)$ を足しあわせたものを $1,000,000,007$ で割った余りを求めてください。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

• $1$ 行目に、 $2$ 個の整数 $N,$ $K$ ($1$ $≦$ $N,$ $K$ $≦$ $109$) がスペース区切りで与えられる。

部分点

この問題は AtCoder Beginner Contest の問題としては非常に難しいため、通常 ($100$ 点満点) と異なり $101$ 点満点であり、部分点が設定されている。

• $5$ 点分のテストケースは $1$ $≦$ $N,$ $K$ $≦$ $100$ を満たす。
• 別の $10$ 点分のテストケースは $1$ $≦$ $N$ $≦$ $104,$ $1$ $≦$ $K$ $≦$ $100$ を満たす。
• さらに別の $85$ 点分のテストケースは $1$ $≦$ $N$ $≦$ $109,$ $1$ $≦$ $K$ $≦$ $100$ を満たす。以上で合計 $100$ 点となる。

出力

標準出力に、求める和を $1,000,000,007$ で割った余りを出力せよ。

末尾の改行を忘れないこと。

入力例1

4 2

出力例1

14

$LCM(1, 2) + LCM(2, 2) + LCM(3, 2) + LCM(4, 2) = 2 + 2 + 6 + 4 = 14$ となります。

入力例2

10000 100

出力例2

865504986

入力例3

1000000000 90

出力例3

50001213

入力例4

1000000000 999999900

出力例4

231285006