这是一次不寻常的比赛中的一个不寻常的问题,这里是公告: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