AT_abc020_d [ABC020D] LCM Rush

[problemUrl]: https://atcoder.jp/contests/abc020/tasks/abc020_d $ 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 $ $ ≦ $ $ 10^9 $) がスペース区切りで与えられる。

標準出力に、求める和を $ 1,000,000,007 $ で割った余りを出力せよ。 末尾の改行を忘れないこと。

### 部分点 この問題は AtCoder Beginner Contest の問題としては非常に難しいため、通常 ($ 100 $ 点満点) と異なり $ 101 $ 点満点であり、部分点が設定されている。 - $ 5 $ 点分のテストケースは $ 1 $ $ ≦ $ $ N, $ $ K $ $ ≦ $ $ 100 $ を満たす。 - 別の $ 10 $ 点分のテストケースは $ 1 $ $ ≦ $ $ N $ $ ≦ $ $ 10^4, $ $ 1 $ $ ≦ $ $ K $ $ ≦ $ $ 100 $ を満たす。 - さらに別の $ 85 $ 点分のテストケースは $ 1 $ $ ≦ $ $ N $ $ ≦ $ $ 10^9, $ $ 1 $ $ ≦ $ $ K $ $ ≦ $ $ 100 $ を満たす。以上で合計 $ 100 $ 点となる。 ### Sample Explanation 1 $ LCM(1,\ 2)\ +\ LCM(2,\ 2)\ +\ LCM(3,\ 2)\ +\ LCM(4,\ 2)\ =\ 2\ +\ 2\ +\ 6\ +\ 4\ =\ 14 $ となります。