CF2089C2 Key of Like (Hard Version)

这是该问题的困难版本。两个版本之间的区别在于，在这个版本中 $$$k$$$ 可以是非零值。只有当你解决了该问题的所有版本时才能进行 hack。 玩具盒如同装满童年欢愉的冰箱。像脆弱、挣扎、希望……当这样的沉睡者被重新唤醒时，会有什么样的惊喜等待？ 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 \leq n \leq 100$$$，$$$1 \leq l \leq 5000$$$，$$$0 \leq k \leq 25$$$）——参与游戏的成员数、锁的数量和仿制钥匙的数量。 保证所有测试用例的 $$$l$$$ 之和不超过 $$$5000$$$。

对于每个测试用例，输出一行包含 $$$n$$$ 个整数 $$$e_1, \ldots, e_n$$$，其中 $$$e_i$$$ 表示第 $$$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$$$。换句话说，输出满足 $$$0 \le x < M$$$ 且 $$$e_i \cdot q \equiv p \pmod{M}$$$ 的整数 $$$e_i$$$。

对于第一个测试用例，只有 $$$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} $$ 翻译由 DeepSeek R1 完成