「GLR-R4」夏至

  「柳庭风静人眠昼，昼眠人静风庭柳」 ---   老 V 说为大家准备了特别的粽子，所以天依来了；   天依来了，所以阿绫来了；   阿绫来了，龙牙也不敢不来；   到了快一半了，于是剩下的大家都来了……   所以，为什么要在模拟演出训练结束后来补文化课啊！   “天依，这数学老师真的在讲数学？”   “摩柯，我和阿绫就靠你了！”天依戳戳前排摩柯的肩膀。   “要推出来了，要推出来了……”，摩柯大概是第一次把草稿纸写得快满，“我知道我很急，但我先别急……这像是在做噩梦一样。” ---   **夏至** 「允许我这一次片刻逃离　偶尔也试着用背影　去面对未来不确定」

  为了鉴定摩柯是不是在做噩梦，请你来解决黑板上的一道简单的数学问题吧！   令积性函数 $f(n)$ 满足 $f(p^c)=p^{\gcd(c,k)}$，其中 $k$ 为给定常数，$p$ 为素数，$c$ 为正整数。现在，给定 $n,m,k$，请求出 $$ \left(\sum_{i=1}^n\sum_{j=1}^mf(i\cdot j)\right)\bmod(10^9+7). $$   对于积性函数的定义，请参考「题意解释」。

输入只有一行包含三个整数，分别表示 $n,m,k$。

一行一个整数，表示答案对 $10^9+7$ 取模后的值。

2 2 64

9

5 5 64 

213

1234 1234 12

673319736

30000 10000000 2

836094021

#### 题意解释   对于数论函数 $f(n)$ 和任意两个互素的正整数 $x,y$，若恒有 $f(xy)=f(x)f(y)$，则称 $f(n)$ 为积性函数。   当已知积性函数 $f(n)$ 在所有素数幂处的取值时，我们可以计算任意正整数的函数值。具体地，对于 $n>1$，设 $n$ 的**唯一分解**形式为 $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$，则有 $f(n)=f(p_1^{\alpha_1})f(p_2^{\alpha_2})\cdots f(p_k^{\alpha_k})$。 ### 数据规模与约定 对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le m\le 10^{10}$，$1\le k\le 10^{9}$。 对于不同的子任务，作如下约定： | 子任务编号 | $n$ | $m$ | $k$ | 子任务分值 | | :--------: | :----------------: | :-----------: | :----------: | :--------: | | $1$ | $\le 10^3$ | $\le 10^3$ | $\le 10^{3}$ | $5$ | | $2$ | $=1$ | $\le 10^{10}$ | $\le 10^9$ | $15$ | | $3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^9$ | $15$ | | $4$ | $\le 500$ | $\le 10^9$ | $\le 10^9$ | $10$ | | $5$ | $\le10^5$ | $\le 10^{10}$ | $=1$ | $15$ | | $6$ | $\le 5\times 10^3$ | $\le 10^9$ | $\le 10^9$ | $15$ | | $7$ | $\le 5\times 10^4$ | $\le 10^8$ | $\le 10^9$ | $15$ | | $8$ | $\le 10^5$ | $\le 10^{10}$ | $\le 10^9$ | $10$ |