CF1924E Paper Cutting Again

有一张初始高度为 $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)$。

每组测试数据包含多组测试用例。第一行包含测试用例数 $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$。

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

对于第一个测试用例，面积已经小于 $10$，所以不需要裁剪。 对于第二个测试用例，面积正好为 $8$，任意 $4$ 条可选裁剪线中的一条都能使面积严格小于 $8$。 对于第三个测试用例，最终答案为 $\frac{17}{6} = 833\,333\,342\bmod (10^9+7)$。 对于第四个测试用例，最终答案为 $\frac{5}{4} = 250\,000\,003\bmod (10^9+7)$。 由 ChatGPT 4.1 翻译