F. Boki-chan Who Dislikes Mathematics
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

With nothing to do, Boki-chan opened a primary school math Olympiad book and couldn't help but get immersed in it...

Boki-chan defined a function:

$$$$$$ Bq(x,y,v)=\operatorname{d}(\gcd(x,y))^{[\operatorname{d}(\gcd(x,y)) \leq v]} $$$$$$

Boki-chan has $$$ q $$$ queries, and for each query, $$$ n, m, v $$$ will be given. For each query, you need to calculate:

$$$$$$ \prod_{i=1}^n \prod_{j=1}^m Bq(i,j,v) $$$$$$

The answer should be taken modulo $$$10^9 + 7$$$.

  • Here, we denote $$$ \operatorname{d}(x) $$$ as the number of divisors of $$$x$$$, and $$$ \gcd(x,y) $$$ as the greatest common divisor of $$$ x $$$ and $$$ y $$$.
  • Let $$$ [P] = x $$$, where $$$ P $$$ is a proposition. If $$$P$$$ is true, then $$$x = 1$$$; if $$$P$$$ is false, then $$$x = 0$$$.
Input

First, input a line with an integer $$$ q(1 \leq q \leq 2 \times 10^3 )$$$, representing the number of queries from Boki-chan.

Next, $$$ q $$$ lines follow, each containing three integers $$$ n,m,v( 1 \leq n,m,v \leq 2\times 10^5)$$$.

Output

Output a line with $$$ q $$$ integers, where the $$$ i $$$-th integer represents the answer to the $$$ i $$$-th query. The answer should be taken modulo $$$10^9+7$$$.

Example
Input
2
2 2 10
10 10 3
Output
2 973087142