题目描述

在电脑的帮助下你轻松就赢得了第一轮的游戏，但显然你觉得这游戏太无聊了……于是你就想退出游戏。

当然英雄们是不会轻易抛弃你的，不过在你的强烈抗议下，他们不得不作出一些让步：只要你能做出他们的难题，他们就放过你，允许你退出游戏。

这道难题是这样的：

给出 $n,k$ ，求出下面这个式子的值：

$$\sum_{i=1}^n\sum_{j=1}^n \sigma_k(ij)$$

其中 $\sigma_k(ij)$ 表示 $i\times j$ 的所有约数的 $k$ 次方之和，即 $\sum_{d|ij}d^k$ 。
考虑到答案可能非常大，因此你只需要求出答案对 $10^9+7$ 取模后的值即可。

英雄们说完题面之后就开始等着看你的笑话，然而你怎么可能会被这道题目难倒呢？

输入格式

一行两个整数，分别表示 $n$ 和 $k$ 。

输出格式

一行一个整数，表示答案。

样例

2 2

32

经计算可得 $\sigma_2(1)=1^2=1,\sigma_2(2)=1^2+2^2=5,\sigma_2(4)=1^2+2^2+4^2=21$ ，因此答案即为 $\sigma_2(1)+\sigma_2(2)+\sigma_2(2)+\sigma_2(4)=1+5+5+21=32$ 。

数据范围与提示

对于 $20\%$ 的数据， $n\le 10^3$ ， $k\le 5$ ；
对于 $50\%$ 的数据， $n\le 10^6$ ， $k\le 50$ ；
对于另 $10\%$ 的数据， $k=0$ ，同时保证对于其他数据均有 $k>0$ ；
对于另 $10\%$ 的数据， $k=1$ ；
对于 $100\%$ 的数据， $n\le 10^{10}$ ， $0\le k\le 7\times 10^3$ 。

由于某些原因，本题代码长度限制为 $10$ KB ，评测时会用 Special Judge 对提交的代码长度进行检测。

题解&标程