← 返回题目列表

Codeforces · 1924/E

E. 再次剪纸

中文机器翻译题面 查看原题

有一张矩形纸,初始高度为 $$$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$$$)。测试用例的描述如下。

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

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

输出

对于每个测试用例,打印一个整数 - 问题的答案。

示例

输入 #1

4
2 4 10
2 4 8
2 4 2
2 4 6

输出 #1

0
1
833333342
250000003

注意

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

对于第二个测试用例,面积恰好为 $$$8$$$,因此 $$$4$$$ 可能的削减中的任何一个都会使面积严格小于 $$$8$$$。

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

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