CF1924E.Paper Cutting Again

There is a rectangular sheet of paper with initial height $n$ and width $m$. Let the current height and width be $h$ and $w$ respectively. We introduce a $xy$-coordinate system so that the four corners of the sheet are $(0, 0), (w, 0), (0, h)$, and $(w, h)$. The sheet can then be cut along the lines $x = 1,2,\ldots,w-1$ and the lines $y = 1,2,\ldots,h-1$. In each step, the paper is cut randomly along any one of these $h+w-2$ lines. After each vertical and horizontal cut, the right and bottom piece of paper respectively are discarded.

Find the expected number of steps required to make the area of the sheet of paper strictly less than $k$. It can be shown that this answer can always be expressed as a fraction $\dfrac{p}{q}$ where $p$ and $q$ are coprime integers. Calculate $p\cdot q^{-1} \bmod (10^9+7)$.

有一张初始高度为 $n$、宽度为 $m$ 的矩形纸片。设当前高度和宽度分别为 $h$ 和 $w$。我们引入一个 $xy$-坐标系，使得纸片的四个顶点坐标为 $(0, 0), (w, 0), (0, h)$ 和 $(w, h)$。该纸片可沿直线 $x = 1,2,\ldots,w-1$（竖直切割线）以及直线 $y = 1,2,\ldots,h-1$（水平切割线）进行裁剪。每一步中，纸片在所有这些 $h+w-2$ 条切割线中随机选择一条进行裁剪；每次竖直裁剪后，右侧部分被丢弃；每次水平裁剪后，下侧部分被丢弃。

求使纸片面积严格小于 $k$ 所需步骤数的期望值。可以证明，该期望值恒可表示为最简分数 $\dfrac{p}{q}$（其中 $p$ 与 $q$ 互质）。请计算 $p\cdot q^{-1} \bmod (10^9+7)$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 57000$). Description of the test cases follows.

The first line of each test case contains 3 integers $n$, $m$, and $k$ ($1 \le n, m \le 10^6$, $2 \le k \le 10^{12}$).

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 57000$）。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m \le 10^6$，$2 \le k \le 10^{12}$）。

保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $10^6$。

For each test case, print one integer — the answer to the problem.

对于每个测试用例，输出一个整数——即该问题的答案。

For the first test case, the area is already less than $10$ so no cuts are required.

For the second test case, the area is exactly $8$ so any one of the $4$ possible cuts would make the area strictly less than $8$.

For the third test case, the final answer is $\frac{17}{6} = 833\,333\,342\bmod (10^9+7)$.

For the fourth test case, the final answer is $\frac{5}{4} = 250\,000\,003\bmod (10^9+7)$.

对于第一个测试用例，面积已经小于 $10$，因此无需切割。

对于第二个测试用例，面积恰好为 $8$，因此任意一种 $4$ 种可能的切割方式均能使面积严格小于 $8$。

对于第三个测试用例，最终答案为 $\frac{17}{6} = 833\,333\,342\bmod (10^9+7)$。

对于第四个测试用例，最终答案为 $\frac{5}{4} = 250\,000\,003\bmod (10^9+7)$。