GCD Power Sum

Given three integers \(n\), \(m\), and \(k\), compute the following sum:

\[ S = \sum_{i=1}^{n} \sum_{j=1}^{m} \gcd(i,j)^k \]

Output the value of \(S\) modulo \(10^9+7\).

inputFormat

The input consists of a single line containing three space-separated integers \(n\), \(m\), and \(k\).

outputFormat

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

sample

3 3 1

12

</p>