问题文

最小公倍数（LCM）是指两个正整数 $a$ 和 $b$ 的倍数中最小的一个。

给定两个正整数 $N$ 和 $K$。求 $1$ 到 $N$ 中所有整数 $i$ 的 $LCM(i, K)$ 的和对 $1,000,000,007$ 取余数。

输入

输入数据从标准输入中按以下格式给出：

$N$ $K$

• 第一行包含两个整数 $N$ 和 $K$，用空格分隔开。
• $1$ 行目，给出两个整数 $N$ 和 $K$ ($1$ $≦$ $N,$ $K$ $≦$ $109$)。

部分点

由于该问题在 AtCoder Beginner Contest 上非常困难，因此设置了部分得分，共计 $101$ 分，与通常的满分（$100$ 分）不同。

• $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