Background

  "The willow courtyard is quiet, people sleep in the daytime; in the daytime people sleep, the quiet wind, the willow courtyard."

---

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

  Tianyi came, so Ayling came;

  Ayling came, and Longya did not dare to stay away either;

  When almost half had arrived, the rest of the others all came too...

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

  "Tianyi, is this math teacher really teaching math?"

  "Moke, Ayling and I are counting on you!" Tianyi poked Moke's shoulder in the front row.

  "I'm about to derive it, I'm about to derive it..." It was probably the first time Moke had almost filled a draft paper, "I know I'm in a hurry, but let me not be in a hurry first... This feels like having a nightmare."

---

  Summer Solstice "Allow me to escape for a short while this one time, and sometimes try to use my back view, to face the uncertainty of the future."

Problem Description

  To check whether Moke 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, and $c$ is a positive integer. Now given $n,m,k$, 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 "Explanation of the Problem".

Input Format

The input contains only one line with three integers, representing $n,m,k$.

Output Format

Output one integer per line, representing the value of the answer modulo $10^9+7$.

2 2 64

9

5 5 64 

213

1234 1234 12

673319736

30000 10000000 2

836094021

Hint

Explanation of the Problem

  For a number-theoretic 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 we know the values of a multiplicative function $f(n)$ at all prime powers, we can compute its value at any positive integer. Specifically, for $n>1$, suppose the unique factorization 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})$.

Constraints and Conventions

For $100\%$ of the testdata, $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:

Subtask ID	$n$	$m$	$k$	Subtask Score
$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$

Translated by ChatGPT 5