← 返回题目列表

Codeforces · 1302/E

E. 惊人的位组

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

这是一次不寻常的比赛中的一个不寻常的问题,这里是公告:http://codeforces.com/blog/entry/73543

Andrey 刚刚开始学习竞争性编程,他对位集及其操作很着迷。

例如,假设他有一个包含 $$$n$$$ 元素的位集。他可以通过以下方式更改位集的值:

1. 他选择不同的索引 $$$i_0$$$, $$$i_1$$$, $$$i_2$$$, ... $$$i_k$$$ ($$$k \geq 1$$$, $$$1 \leq i_j \leq n$$$) 使得位 $$$i_0$$$ 不同于所有位$$$i_1$$$、$$$i_2$$$、...$$$i_k$$$。
2. 他翻转所有这些 $$$k + 1$$$ 位。

如果他可以使用几个这样的更改来翻转所有位,那么他称一个位集令人惊叹。

Andrey 感兴趣的另一个主题是概率论。对于给定的 $$$n$$$ 和 $$$p$$$,其中 $$$p$$$ 是表示为 $$$\frac{a}{b}$$$ 的有理数,其中整数 $$$a, b$$$,他考虑长度为 $$$n$$$ 的所有位集,其中每个元素等于 $$$1$$$,概率 $$$p$$$ 独立于其他元素。

他想知道由所描述的方法生成的位集惊人的概率。

保证这个问题的答案可以表示为有理数 $$$\frac{x}{y}$$$,其中 $$$y$$$ 与 $$$1\,234\,567\,891$$$ 互质。您需要输出这样的整数 $$$z$$$ 使得 $$$x \equiv yz \pmod{1\,234\,567\,891}$$$ 和 $$$0 \leq z < 1\,234\,567\,891$$$。

输入

唯一一行包含三个整数 $$$n, a, b$$$ ($$$1 \leq n \leq 10^9$$$, $$$0 \leq a \leq 10^5$$$, $$$1 \leq b \leq 10^5$$$, $$$a \leq b$$$),表示位集的长度和元素为 $$$1$$$ (概率为 $$$\frac{a}{b}$$$)。

输出

在唯一的一行中输出问题的答案。

示例

输入 #1

5 1 2

输出 #1

848765426

输入 #2

1 228 239

输出 #2

0