最大公约数求和
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

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

其中x \bmod m表示x除以m的余数,\gcd(a,b)表示a和b的最大公约数.

注意对于任意正整数x,均有\gcd(x, 0) = x.

输入描述:

输入一行以空格分隔的两个非负整数n,k(1 \le n \le 2 \times 10^7, 0 \le k \le 10^{18}),请注意n的数据范围.

输出描述:

输出一行一个非负整数代表\sum\limits_{i=1}^n \left( \gcd(i, k) \cdot i^k \right)\left(\bmod 1000000007\right)的结果.
示例1

输入

复制 
3 2

输出

复制 
18

说明

样例中n = 3, k = 2.

答案为(\gcd(1, 2) \cdot 1^2 + \gcd(2, 2) \cdot 2^2 + \gcd(3, 2) \cdot 3^2) \bmod 1000000007 = 1 \cdot 1 + 2 \cdot 4 + 1 \cdot 9 = 18. 

再次提示请注意n的数据范围.