Problem Background

   "Quiet courtyard, people sleep through the day, day sleepers, quiet winds, courtyard willows"

   Old V said he prepared special zongzi for everyone, so Tian Yi came;

   Tian Yi came, so A Ling came;

   A Ling came, so Long Ya didn't dare not to come;

   Almost half of them arrived, so the rest came...

   So, why do we have to catch up on cultural classes after the simulation performance training ends!

   "Tian Yi, is this math teacher really teaching math?"

   "Mo Ke, A Ling and I are counting on you!" Tian Yi poked Mo Ke's shoulder in the front row.

   "I'm about to figure it out, I'm about to figure it out..." Mo Ke probably filled up his draft paper for the first time, "I know I'm in a hurry, but I'll try not to rush... it feels like a nightmare."

   Summer Solstice   "Allow me this brief escape, sometimes try to face the uncertain future with my back turned"

Problem Description

   To determine if Mo Ke is having a nightmare, please solve a simple math problem on the blackboard!

   Let the multiplicative function $f(n)$ satisfy $f(p^c)=p^{\gcd(c,k)}$, where $k$ is a given constant, $p$ is a prime number, and $c$ is a positive integer. Now, given $n, m, k$, please compute
$$ \left(\sum_{i=1}^n\sum_{j=1}^mf(i\cdot j)\right)\bmod(10^9+7). $$

   For the definition of a multiplicative function, please refer to the "Problem Explanation".

Input Format

The input consists of a single line containing three integers, representing $n, m, k$.

Output Format

Output a single integer, which is the answer modulo $10^9+7$.

Sample Input and Output

Sample Input #1

2 2 64

Sample Output #1

9

Sample Input #2

5 5 64

Sample Output #2

213

Sample Input #3

1234 1234 12

Sample Output #3

673319736

Sample Input #4

30000 10000000 2

Sample Output #4

836094021

Notes

Problem Explanation

   For a number theory function $f(n)$ and any two coprime positive integers $x, y$, if it always holds that $f(xy)=f(x)f(y)$, then $f(n)$ is called a multiplicative function.

   When the values of the multiplicative function $f(n)$ at all prime powers are known, we can compute the function value for any positive integer. Specifically, for $n>1$, if the unique factorization form of $n$ is $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$, then $f(n)=f(p_1^{\alpha_1})f(p_2^{\alpha_2})\cdots f(p_k^{\alpha_k})$.

Data Range and Constraints

For $100\%$ of the data, $1 \le n \le 10^5$, $1 \le m \le 10^{10}$, $1 \le k \le 10^9$.

For different subtasks, the following constraints apply:

见题面 Input 部分

见题面 Output 部分