C2. Ключ к удовольствию (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это hard версия задачи. Отличие между версиями заключается в том, что в этой версии $$$k$$$ может быть ненулевым. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Игрушечная коробка — это холодильник, наполненный детскими радостями. Удовольствие, слабость, борьба, надежда ... Когда такой спящий дух пробуждается, какие сюрпризы его ждут?

М получила свою игрушечную коробку в подарок на день рождения от своей матери. Ювелир-дизайнер определенно не пожалел бы усилий, чтобы украсить еще одно бесценное произведение искусства, как звездное небо с изысканно оформленными драгоценными камнями. Кроме того, $$$l$$$ различных замков защищают крошечную вселенную ее любимой дочери: заколка для волос с цветочным дизайном, потертой перьевой ручкой, шариком в форме буквы M ... каждая деталь скрывает драгоценный момент.

Несколько дней назад М заново открыла свою игрушечную коробку, когда она реорганизовала свою спальню, вместе с кольцом ключей, уникально разработанным для игрушечной коробки. На кольце ключей находятся $$$(l + k)$$$ ключей, из которых $$$l$$$ ключей могут открыть один из $$$l$$$ замков соответственно, в то время как другие $$$k$$$ ключей не более чем подделки, чтобы предотвратить атаки методом подбора. Чтобы напомнить о соответствии, мать М украсила каждый ключ драгоценным камнем другого типа. Однако прошедшие дни стерли память М.

«... Так что мне придется обратиться к вам всем,» — сказала М, укладывая это кольцо ключей на стол.

К поднял ключи и внимательно их осмотрел. «Внешний вид этих ключей не раскрывает ничего полезного. Поэтому, боюсь, нам придется проверять их последовательно.»

Хотя все желают помочь М, никто не имеет плана. Наблюдая за реакциями других, Т предложил: «Давайте сыграем в игру. Каждый по очереди пробует ключ, и тот, кто откроет больше всего замков, будет удивительным.»

$$$n$$$ участников, включая саму М, по очереди пытаются открыть игрушечную коробку рекурсивно в том же порядке, пока все $$$l$$$ замков не будут открыты. На каждом ходе текущий участник выбирает только один ключ и тестирует его на одном из замков. Чтобы открыть игрушечную коробку как можно скорее, каждый участник выбирает ключ и замок, которые максимизируют вероятность успешного совпадения. Если есть несколько таких пар, участник случайным образом выбирает одну из таких пар с равной вероятностью. Очевидно, если замок был сопоставлен с ключом, то ни замок, ни ключ не будут выбраны снова в следующих попытках.

Предположим, что в самом начале вероятность того, что замок может быть открыт любым ключом, равна. Если все всегда пробуют оптимальные пары ключей и замков на основе всех исторических испытаний, каково будет ожидаемое количество успешных совпадений для каждого участника?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$T$$$ ($$$1 \le T \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка входных данных содержит три целых числа, $$$n$$$, $$$l$$$, $$$k$$$ ($$$1 \leq n \leq 100, 1 \leq l \leq 5000, 0 \leq k \leq 25$$$) — количество участников, принимающих участие в игре, количество замков и количество поддельных ключей.

Гарантируется, что сумма $$$l$$$ по всем наборам входных данных не превосходит $$$5000$$$.

Выходные данные

Для каждого набора входных данных выведите одну строку с $$$n$$$ целыми числами $$$e_1, \ldots, e_n$$$, где $$$e_i$$$ представляет ожидаемое количество успешных совпадений, по модулю $$$10^9 + 7$$$.

Формально, пусть $$$M = 10^9 + 7$$$. Можно показать, что точный ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, и $$$q \not \equiv 0 \pmod{M}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$e_i$$$, что $$$0 \le x \lt M$$$ и $$$e_i \cdot q \equiv p \pmod{M}$$$.

Пример
Входные данные
4
3 1 4
3 2 0
25 2 5
4 102 9
Выходные данные
800000006 800000006 400000003
500000004 1 500000004
142857144 166666668 615646263 639455787 234126986 257936510 195918369 502040820 478316330 81264173 190523433 471438023 23809524 0 0 0 0 0 0 0 0 0 0 0 0
568832210 85779764 969938175 375449967
Примечание

Для первого набора входных данных есть только $$$1$$$ замок, поэтому стратегия всегда будет заключаться в выборе любого ключа, который никто никогда не пробовал. Поскольку всего $$$1 + 4 = 5$$$ ключей, вероятность того, что каждый участник успешно откроет замок, составит $$$2/5, 2/5, 1/5$$$ соответственно, что также является ожидаемыми числами успешных совпадений.

Для второго набора входных данных есть ровно $$$2$$$ замка и $$$2$$$ ключа, при этом каждый ключ соответствует одному из замков. Без дополнительной информации первый участник случайным образом выбирает ключ и замок с равными вероятностями, для которых вероятность успеха составляет $$$1/2$$$.

  • Если первый участник успешен, второй участник откроет другой замок с другим ключом.
  • Если первый участник неудачен, то выбранный им ключ может открыть другой замок, а другой ключ должен соответствовать замку, который он выбрал. Эта информация позволяет как второму, так и третьему участнику открыть замок.

В заключение, ожидаемые числа успешных совпадений будут:

$$$$$$ \begin{split} e_1 &= \frac{1}{2}\times 1 + \frac{1}{2}\times 0 = \frac{1}{2} \equiv 500,000,004 \pmod {10^9+7},\\ e_2 &= \frac{1}{2}\times 1 + \frac{1}{2} \times 1 = 1,\\ e_3 &= \frac{1}{2}\times 0 + \frac{1}{2} \times 1 = \frac{1}{2} \equiv 500,000,004\pmod {10^9+7}. \end{split} $$$$$$