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