Background

Special for beginners, ^_^

Description

给定非负整数n, k, 请计算$\sum\limits_{i=1}^n \left( \gcd(i, k) \cdot i^k \right)\left(\bmod 1000000007\right)$。

Format

Input

输入一行以空格分隔的两个非负整数n（$1 \le n \le 2 \times 10^7$）和k（$0 \le k \le 10^{18}$）。

Output

输出一行一个非负整数代表和（对1e9+7取模）。

Samples

3 2

18

Limitation

1s, 1024KiB for each test case.