Counting Exponential Equation Triples

You are given T test cases. In each test case, you are given three positive integers A, B, and C. For each test case, count the number of triples (x, y, z) satisfying:

$$ \Big(\sum_{x=1}^{A}\sum_{y=1}^{B}\sum_{z=1}^{C} [y^x = x^z]\Big) \bmod (10^9+7), $$

where \([P]\) is the indicator function that equals 1 if the proposition P is true and 0 otherwise.

Explanation:

• Case x = 1: The equation becomes y¹ = 1^z = 1. Hence, we must have y = 1 and any z (from 1 to C) gives a valid triple.
• Case x > 1: The equality y^x = x^z imposes a relation between x and y. It can be proved that a necessary and sufficient condition is that there exists a positive integer t and integers p,q (with q ≥ 1) such that
  x = t^q, y = t^p and then the equation becomes:
  $$ (t^p)^{t^q} = (t^q)^z \Longrightarrow z = \frac{p\,t^q}{q}. $$
• The triple \((x,y,z)\) is valid if and only if:
  • For x = t^q we have \(1 \le t^q \le A\).
  • For y = t^p we have \(1 \le t^p \le B\).
  • \(z = \frac{p\,t^q}{q}\) is an integer and \(1 \le z \le C\).

Task: Compute the number of valid triples \((x, y, z)\) modulo \(10^9+7\) for each test case.

inputFormat

The first line contains an integer T (the number of test cases). Each of the next T lines contains three space‐separated integers: A, B, and C.

Constraints (for the scope of this problem, you may assume the ranges are small enough to allow a solution with a triple nested iteration on x and a inner loop on possible exponents):

• 1 \(\le\) T \(\le\) 100
• 1 \(\le\) A, B, C \(\le\) 10³

outputFormat

For each test case, output a single line containing the required answer: the count of triples \((x,y,z)\) satisfying the equation modulo \(10^9+7\).

sample

4
4 4 4
1 1 10
5 10 10
2 2 2

9
10
19
1

</p>