题目背景

  「柳庭风静人眠昼，昼眠人静风庭柳」

---

  老 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}$	$5$
$2$	$=1$	$\le 10^{10}$	$\le 10^9$	$15$
$3$	$\le 10^5$
$4$	$\le 500$	$\le 10^9$		$10$
$5$	$\le10^5$	$\le 10^{10}$	$=1$	$15$
$6$	$\le 5\times 10^3$	$\le 10^9$	$\le 10^9$
$7$	$\le 5\times 10^4$	$\le 10^8$
$8$	$\le 10^5$	$\le 10^{10}$		$10$