Description

  为了鉴定摩柯是不是在做噩梦，请你来解决黑板上的一道简单的数学问题吧！

  令积性函数 $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).$$

  对于积性函数的定义，请参考「题意解释」。

Input Format

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

Output Format

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

2 2 64

9

5 5 64 

213

1234 1234 12

673319736

30000 10000000 2

836094021

Hint

题意解释

  对于数论函数 $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$