← 返回题目列表

Codeforces · 913/F

F. 强关联锦标赛

中文机器翻译题面 查看原题

好城有一场国际象棋锦标赛。 n名选手被邀请参加比赛。锦标赛按以下规则举行:

1. 最初,每个玩家与其他玩家玩一场游戏。没有任何关系;
2. 之后,组织者构建一个以玩家为顶点的完整有向图。对于每一对玩家来说,他们之间都存在一条有向边:游戏的获胜者是该边的起点,失败者是该边的终点;
3. 之后,组织者构建了该图的浓缩。该图的凝聚是一个无环完全图,因此它具有唯一的由初始图 A1 → A2 → ... → Ak 的强连通分量组成的哈密顿路径。
4. 第一个组件 A1 的玩家被放置在第一个 $$|A_{1}|$$ 位置,来自组件 A2 的玩家被放置在接下来的 $$|A_{2}|$$ 位置,依此类推。
5. 为了确定每个玩家在强连接组件中的确切位置,在每个组件内递归地重复从 1 到 5 的所有过程,即对于来自组件 Ai 的每个 i = 1, 2, ..., k 玩家再次互相玩游戏,依此类推;
6. 如果一个组件由一个玩家组成,那么他没有更多的对手,他的位置已经确定,并且该过程停止。

玩家用 1 到 n 的整数进行枚举。该枚举是根据之前锦标赛的结果进行的。已知玩家 i 以概率 p 赢得玩家 j (i < j)。

您需要帮助组织锦标赛。求所有玩家玩的游戏总数的期望值。

可以证明,答案可以表示为 $$\frac{p}{q}$$,其中 P 和 Q 是互质整数,$$Q \not\equiv 0 \pmod{998244353}$$。打印 P·Q - 1 模 998244353 的值。

如果您不熟悉上述任何术语,可以在此处阅读相关内容。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 2000) — 玩家数量。

第二行包含两个整数 a 和 b (1 ≤ a < b ≤ 100) — 分数 $$\frac{a}{b} = p$$ 的分子和分母。

输出

在唯一的一行中打印所有玩家玩的游戏总数的期望值。使用上述格式打印答案。

示例

输入 #1

3
1 2

输出 #1

4

输入 #2

3
4 6

输出 #2

142606340

输入 #3

4
1 2

输出 #3

598946623

注意

在第一个示例中,预期值为 4。

在第二个示例中,预期值为 $$\frac{27}{7}$$。

在第三个示例中,预期值为 $${ \frac { 5 6 } { 5 } }$$。