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

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

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

М получила свою игрушечную коробку в подарок на день рождения от своей матери. Ювелир-дизайнер определенно не пожалел бы усилий, чтобы украсить еще одно бесценное произведение искусства, как звездное небо с изысканно оформленными драгоценными камнями. Кроме того, $$$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, k = 0$$$) — количество участников, принимающих участие в игре, количество замков и количество поддельных ключей.

Гарантируется, что сумма $$$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 0
3 2 0
2 5 0
9 104 0
Выходные данные
1 0 0
500000004 1 500000004
200000004 800000008
869203933 991076635 39374313 496894434 9358446 51822059 979588764 523836809 38844739
Примечание

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

Для второго набора входных данных есть ровно $$$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} $$$$$$