#6207. 米缇

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: AntiLeaf

题目描述

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

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

这道难题是这样的:


给出 $ 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 对提交的代码长度进行检测。 **

题解&标程