Есть прямоугольный лист бумаги с начальной высотой \(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)\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — ответ на задачу.
Примечание
Для первого тестового случая площадь уже меньше \(10\), поэтому дополнительные разрезы не требуются.
Для второго тестового случая площадь точно равна \(8\), поэтому любой из \(4\) возможных разрезов сделает площадь строго меньше \(8\).
Для третьего тестового случая окончательный ответ равен \(\frac{17}{6} = 833\,333\,342\bmod (10^9+7)\).
Для четвертого тестового случая окончательный ответ равен \(\frac{5}{4} = 250\,000\,003\bmod (10^9+7)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 4 10
2 4 8
2 4 2
2 4 6
|
0
1
833333342
250000003
|