#P18559. Quad Kingdoms Chess 2
Quad Kingdoms Chess 2
Quad Kingdoms Chess 2
四国棋(Quad Kingdoms Chess,简称 QKC)在技术锤子大学(Technical Hammer University,简称 THU)的 605A 宿舍中非常流行。
小青鱼在这所很棒的大学里有很多朋友。今天,经过一天的课程,小 X 和小 Y 决定下一盘四国棋。

遗憾的是,他们没能凑齐四名玩家——小青鱼并不会下四国棋!为了找点乐子,他们各自随意拿了一组棋子,开始了比较棋子强弱的简化游戏。
每枚普通棋子用整数 表示。小 X 和小 Y 各有一组棋子,按照以下规则进行对战:
- 最初,双方各自把棋子排成一个序列,再分别独立、均匀随机地打乱。
- 双方各派出自己序列中的第一枚棋子,分别记为 和 。
- 若 ,小 Y 的棋子被消灭,必须派出序列中的下一枚棋子;小 X 当前的棋子继续留在场上。
- 若 ,小 X 的棋子被消灭,必须派出序列中的下一枚棋子;小 Y 当前的棋子继续留在场上。
- 若 ,双方当前棋子都被消灭,双方都派出各自序列中的下一枚棋子。
在任何时刻,如果一方已经无法派出棋子,而另一方仍有至少一枚棋子,则仍有棋子的一方获胜。如果双方同时耗尽棋子,则为平局。
小青鱼觉得这太简单了!于是,在洗牌之前,他偷偷向小 X 的棋子中加入了 枚额外的炸弹。也就是说,小 X 现在有 枚普通棋子和 枚炸弹,共 枚棋子。炸弹与任意一枚对方棋子交战时,双方都被消灭。
给定双方的普通棋子,求小 X 获胜、小 Y 获胜以及平局的概率,对 取模。
输入格式
第一行三个整数 (,),分别表示小 X 普通棋子的数量、小 Y 棋子的数量以及小青鱼加入的炸弹数量。
第二行 个整数 (),表示小 X 的普通棋子强度。
第三行 个整数 (),表示小 Y 的棋子强度。
本题只有一组输入。相同强度的棋子可以重复。
输出格式
第一行输出 ,表示小 X 获胜的概率模 。
第二行输出 ,表示小 Y 获胜的概率模 。
第三行输出 ,表示平局的概率模 。
若概率约分后为 ,模意义的值为 ,输出其 内的代表元。
原样例 1
5 5 1
11 4 2 11 9
20 1 6 20 1
0
1
0
原样例 2
8 7 5
58 42 34 58 12 12 9 1
28 59 59 1 36 14 7
695057094
239873545
63313715
原样例 3
8 7 5
9 1 2 12 7 7 7 6
15 4 15 1 15 11 13
673575784
13961460
310707110