Problem Statement

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

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

Input

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

N K

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

部分点

この問題は 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$ 点となる。

Output

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

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