题目描述

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

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

这道难题是这样的：

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

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

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

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

输入格式

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

输出格式

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

样例

input

2 2

output

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

题解&标程