C. 小 Y 和恐怖的奴隶主

小 Y 是一个喜欢玩游戏的 OIer。一天，她正在玩一款游戏，要打一个 Boss。

虽然这个 Boss 有 点生命值，但它只带了一个随从——一个只有 点生命值的「恐怖的奴隶主」。

这个「恐怖的奴隶主」有一个特殊的技能：每当它被扣减生命值但没有死亡（死亡即生命值 ），且 Boss 的随从数量小于上限 ，便会召唤一个新的具有 点生命值的「恐怖的奴隶主」。

现在小 Y 可以进行 次攻击，每次攻击时，会从 Boss 以及 Boss 的所有随从中的等概率随机选择一个，并扣减 点生命值，她想知道进行 次攻击后扣减 Boss 的生命值点数的期望。为了避免精度误差，你的答案需要对 取模。

输入第一行包含三个正整数 ， 表示询问组数， 的含义见题目描述。

接下来 行，每行包含一个正整数 ，表示询问进行 次攻击后扣减 Boss 的生命值点数的期望。

输出共 行，对于每个询问输出一行一个非负整数，表示该询问的答案对 取模的结果。

可以证明，所求期望一定是一个有理数，设其为 （），那么你输出的数 要满足 。

样例 1

输入

3 2 6
1
2
3

输出

499122177
415935148
471393168

样例 1 解释

对于第一次询问，第一次攻击有 的概率扣减 Boss 的生命值，有 的概率扣减随从的生命值，所以答案为 。。

对于第二次询问，如果第一次攻击扣减了 Boss 的生命值，那么有 的概率第二次攻击仍扣减 Boss 的生命值，有 的概率第二次攻击扣减随从的生命值；如果第一次攻击扣减了随从的生命值，那么现在又新召唤了一个随从（「恐怖的奴隶主」），于是有 的概率第二次攻击扣减 Boss 的生命值，有 的概率第二次攻击扣减随从的生命值。所以答案为 。。

样例 2

见附加文件下的 ex_2.in 与 ex_2.ans。

该组样例的数据范围（除询问组数 外）同第 7、8 个测试点。

在所有测试点中，。

各个测试点的分值和数据范围如下：