再次裁纸

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

初始有一张高为 $n$、宽为 $m$ 的矩形纸。当前纸张高为 $h$、宽为 $w$ 时，可以沿 $x=1,2,\ldots,w-1$ 或 $y=1,2,\ldots,h-1$ 裁剪；每一步在这 $h+w-2$ 条直线中等概率随机选择一条。竖直裁剪后丢弃右侧部分，水平裁剪后丢弃下方部分。

求纸张面积严格小于 $k$ 前所需裁剪次数的期望。若期望写成最简分数 $p/q$，输出 $p\cdot q^{-1}\bmod(10^9+7)$。

输入格式

第一行一个整数 $t$，表示测试用例数。随后 $t$ 行，每行三个整数 $n,m,k$。

输出格式

对每个测试用例输出一行一个整数。

样例输入 1

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

样例输出 1

0
1
833333342
250000003

数据范围

对于全部数据，$1\le t\le57000$，$1\le n,m\le10^6$，$2\le k\le10^{12}$，且所有测试用例的 $n$ 之和与 $m$ 之和分别不超过 $10^6$。

题目来源：Codeforces 1924E。