C2. 钥匙与锁（困难版）
每个测试点时间限制：3 秒
内存限制：512 兆字节

这是该问题的困难版本。与简单版本的区别在于，此版本中 $k$ 可以不为 $0$。只有当你解决了该问题的所有版本时，才可以进行 Hacking。

一个玩具盒是一个装满童年欢乐的冰箱。像热爱、挣扎、希望……当这样一个沉睡的东西被重新唤醒时，会有怎样的惊喜在等着呢？

M 从她母亲那里收到玩具盒作为生日礼物。一位珠宝设计师一定会不遗余力地把又一件无价的杰作装饰成繁星点点的天空，用精致切割的宝石。此外，$l$ 把不同的锁保护着小女儿那微小宇宙里珍贵的瞬间：一个花朵造型的发夹、一支风化羽毛笔、一个 M 形的气球……每件物品都藏着一个宝贵的回忆。

几天前，M 在整理卧室时重新发现了她的玩具盒，还有一串为玩具盒特别设计的钥匙。钥匙串上一共有 $(l + k)$ 把钥匙，其中 $l$ 把钥匙能恰好打开 $l$ 把锁中的一把，另外 $k$ 把钥匙只是用来阻止暴力攻击的仿制品。为了帮助记忆，M 的母亲在每把钥匙上镶嵌了不同类型宝石。然而，时光流逝，M 的记忆已经模糊。

“……所以我必须求助于你们大家。”M 把钥匙串放在桌上说。

K 拿起钥匙仔细检查：“这些钥匙的外观揭示不了任何有用的信息。因此，恐怕我们只能一个一个地尝试。”

虽然每个人都想帮助 M，但没有人有计划。看到大家的反应，T 建议道：“让我们玩个游戏吧。每个人轮流试一把钥匙，谁打开的锁最多谁就赢了。”

包括 M 在内的 $n$ 个人按照相同的顺序轮流依次解锁，直到所有 $l$ 把锁都被打开。在每个回合中，当前的人只选择一把钥匙并在一把锁上测试。为了尽快打开玩具盒，每个人都会选择当前最可能匹配成功的钥匙与锁的组合。如果有多个最优的组合，他会随机从中选择一个，每个组合被选中的概率相等。显然，如果一把锁已经被匹配过，它或与它配对的钥匙都不会在后续尝试中再被使用。

假设在最开始时，任意一把锁被某把钥匙打开的概率是相等的。如果每个人都基于所有历史的尝试，总是选择最有可能成功的钥匙‑锁配对，那么每个人期望的匹配成功锁的数量是多少？

---

输入格式

每个测试文件包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例只有一行，包含三个整数 $n$，$l$，$k$
（$1 \le n \le 100$，$1 \le l \le 5000$，$0 \le k \le 25$）
—— 人数、锁的数量和仿制品的数量。

保证所有测试用例的 $l$ 之和不超过 $5000$。

---

输出格式

对于每个测试用例，在一行中输出 $n$ 个整数 $e_1, e_2, \dots, e_n$，其中 $e_i$ 表示第 $i$ 个人期望的匹配成功（打开的锁）数量，对 $10^9+7$ 取模。

换句话说，设 $M = 10^9+7$。可以证明准确的期望可以表示为不可约分数 $\frac{p}{q}$，其中 $p$、$q$ 是整数且 $q \not\equiv 0 \pmod M$。输出整数 $e_i$ 满足 $0 \le e_i < 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$ 把钥匙，所以每个成员成功打开锁的概率分别是 $\frac{2}{5}, \frac{2}{5}, \frac{1}{5}$，这些也是他们期望成功匹配的数量。

对于第二组测试用例，恰有 $2$ 把锁和 $2$ 把真钥匙，每把钥匙对应一把锁。因为没有任何额外信息，第一个成员随机选择一把钥匙和一把锁，成功概率为 $\frac{1}{2}$。

• 如果第一个人成功：第二个人会用另一把钥匙打开另一把锁。
• 如果第一个人失败：则她选的钥匙可以打开另一把锁，且另一把钥匙必然对应她选的那把锁。
  这个信息使得第二个人和第三个人都能打开一把锁。

因此期望成功数量为：

$$e_1 = \frac{1}{2} \times 1 + \frac{1}{2} \times 0 = \frac{1}{2} \equiv 500000004 \pmod{10^9+7} $$$$e_2 = \frac{1}{2} \times 1 + \frac{1}{2} \times 1 = 1 \equiv 1 $$$$e_3 = \frac{1}{2} \times 0 + \frac{1}{2} \times 1 = \frac{1}{2} \equiv 500000004 \pmod{10^9+7} $$