Multiplicative Function Sum

To determine if Moko is experiencing a nightmare, solve the following mathematical problem on the board!

Let f(n) be a multiplicative function defined by the rule $$ f(p^c)=p^{\gcd(c,k)}, $$ where k is a given constant, p is a prime and c is a positive integer. For a general positive integer n with prime factorization \(n=\prod_{i} p_i^{c_i}\), the function is defined multiplicatively as $$ f(n)=\prod_{i} f(p_i^{c_i})=\prod_{i} p_i^{\gcd(c_i,k)}. $$

Given three positive integers n, m and k, compute $$ S = \left( \sum_{i=1}^{n} \sum_{j=1}^{m} f(i \cdot j) \right) \bmod (10^9+7). $$

Note: The function f(n) is defined to be multiplicative, i.e. if a and b are coprime then \(f(ab)=f(a)f(b)\). For n=1, define f(1)=1.

inputFormat

The input consists of a single line containing three space-separated positive integers: n, m, and k.

outputFormat

Output a single integer which is the value of \(S\) modulo \(10^9+7\).

sample

1 1 1

1