311035: CF1924E. Paper Cutting Again
Description
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)$.
InputEach 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$.
OutputFor each test case, print one integer — the answer to the problem.
ExampleInput4 2 4 10 2 4 8 2 4 2 2 4 6Output
0 1 833333342 250000003Note
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)$.
Output
题目描述了一种剪纸游戏，有一张初始高度为 $ n $ 和宽度为 $ m $ 的矩形纸张。纸张的四个角在坐标系中的位置分别为 $ (0, 0), (w, 0), (0, h) $ 和 $ (w, h) $。纸张可以在 $ x = 1,2,\ldots,w-1 $ 和 $ y = 1,2,\ldots,h-1 $ 的线上裁剪。每次裁剪都是随机选择这 $ h+w-2 $ 条线中的一条进行。每次垂直或水平裁剪后，被裁剪下的右部和底部纸张会被丢弃。要求计算使得纸张面积严格小于 $ k $ 所需的预期裁剪步骤数。这个答案可以表示为两个互质整数 $ p $ 和 $ q $ 的分数 $ \frac{p}{q} $。需要计算 $ p \cdot q^{-1} \mod (10^9+7) $。
输入输出数据格式：
输入：
- 第一行包含一个整数 $ t $，表示测试用例的数量，$ t $ 的范围是 $ 1 \le t \le 57000 $。
- 每个测试用例包含一行，包含三个整数 $ n $, $ m $, 和 $ k $，$ n $ 和 $ m $ 的范围是 $ 1 \le n, m \le 10^6 $，$ k $ 的范围是 $ 2 \le k \le 10^{12} $。
- 保证所有测试用例中 $ n $ 和 $ m $ 的总和不超过 $ 10^6 $。
输出：
- 对于每个测试用例，输出一个整数，即问题的答案。
示例输入输出：
输入：
```
4
2 4 10
2 4 8
2 4 2
2 4 6
```
输出：
```
0
1
833333342
250000003
```
注意：
- 第一个测试用例中，纸张面积已经小于 10，所以不需要裁剪。
- 第二个测试用例中，纸张面积正好是 8，所以任何一种裁剪都会使得面积严格小于 8。
- 第三个测试用例的最终答案是 $ \frac{17}{6} = 833\,333\,342 \mod (10^9+7) $。
- 第四个测试用例的最终答案是 $ \frac{5}{4} = 250\,000\,003 \mod (10^9+7) $。题目大意： 题目描述了一种剪纸游戏，有一张初始高度为 $ n $ 和宽度为 $ m $ 的矩形纸张。纸张的四个角在坐标系中的位置分别为 $ (0, 0), (w, 0), (0, h) $ 和 $ (w, h) $。纸张可以在 $ x = 1,2,\ldots,w-1 $ 和 $ y = 1,2,\ldots,h-1 $ 的线上裁剪。每次裁剪都是随机选择这 $ h+w-2 $ 条线中的一条进行。每次垂直或水平裁剪后，被裁剪下的右部和底部纸张会被丢弃。要求计算使得纸张面积严格小于 $ k $ 所需的预期裁剪步骤数。这个答案可以表示为两个互质整数 $ p $ 和 $ q $ 的分数 $ \frac{p}{q} $。需要计算 $ p \cdot q^{-1} \mod (10^9+7) $。 输入输出数据格式： 输入： - 第一行包含一个整数 $ t $，表示测试用例的数量，$ t $ 的范围是 $ 1 \le t \le 57000 $。 - 每个测试用例包含一行，包含三个整数 $ n $, $ m $, 和 $ k $，$ n $ 和 $ m $ 的范围是 $ 1 \le n, m \le 10^6 $，$ k $ 的范围是 $ 2 \le k \le 10^{12} $。 - 保证所有测试用例中 $ n $ 和 $ m $ 的总和不超过 $ 10^6 $。 输出： - 对于每个测试用例，输出一个整数，即问题的答案。 示例输入输出： 输入： ``` 4 2 4 10 2 4 8 2 4 2 2 4 6 ``` 输出： ``` 0 1 833333342 250000003 ``` 注意： - 第一个测试用例中，纸张面积已经小于 10，所以不需要裁剪。 - 第二个测试用例中，纸张面积正好是 8，所以任何一种裁剪都会使得面积严格小于 8。 - 第三个测试用例的最终答案是 $ \frac{17}{6} = 833\,333\,342 \mod (10^9+7) $。 - 第四个测试用例的最终答案是 $ \frac{5}{4} = 250\,000\,003 \mod (10^9+7) $。