现在有 条带有圣盾的胖头鱼，每次敌人会对一只胖头鱼攻击。
「攻击」：在炉石中，若随从 具有 点攻击力，随从 具有 点攻击力，则 攻击 后 受到 点伤害， 受到 点伤害。
「圣盾」：当拥有圣盾的胖头鱼受到伤害时，免疫这条鱼所受到的本次伤害。免疫伤害后，圣盾被破坏。
「胖头鱼」：在一条胖头鱼的圣盾被破坏后，给予其他所有没有圣盾的胖头鱼圣盾。初始时攻击力为 点，由于滑油机器人的存在，所以每次失去圣盾后这头胖头鱼的攻击力提升 点。（与游戏中不同的是，此题先计算加攻再计算伤害）
但为了防止胖头鱼阵型过于赖皮，所以在暗中提高了连续攻击同一只胖头鱼的概率。
具体地开始时所有胖头鱼的权重为 ，假设上次被攻击的胖头鱼已经被连续攻击了 次，那么它的权重变为 ，每只胖头鱼被攻击的概率等于它的权重和除以所有胖头鱼的权重和（如果一头鱼没有被攻击那么权重会回到 ）。
假设所有胖头鱼都不会死亡，现在对于 求在敌人攻击 次后敌人期望受到的伤害和。

一行，输入三个整数 。

输出  行每行一个整数，第  行表示在敌人攻击  次后敌人期望受到的伤害和。
答案可以表示为  的形式（） 的形式，而你需要输出  在模  意义下的值。

1 5 2

10
20
30
40
50

2 3 2

10
20
887328344

3 5 1

9
18
873463836
18717118
311015552

对于可能看不懂题目的人这里给出一种情况的解释：
对于 
依次攻击编号为  的胖头鱼。
第一次胖头鱼  失去圣盾，攻击变为 ，它造成伤害  ，概率是 。
第二次胖头鱼  获得圣盾，胖头鱼  失去圣盾，攻击变为 ，它造成伤害 ，概率是 。
第三次胖头鱼  攻击力不变，它造成伤害  ，概率是 。
第四次胖头鱼  获得圣盾，胖头鱼  失去圣盾，攻击力变为 ，它造成伤害  ，概率是 。
第五次胖头鱼  攻击力不变，受到一次伤害，它造成伤害  ，概率是 。
所有胖头鱼总共受伤  次，结束这个过程，造成总共伤害为  ，概率为 。