Mocha 的数据包

题号：NC219001
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Mocha 沉迷发送数据包，她一共需要发送 $n$ 个相同的数据包。

Mocha 可以进行任意次如下操作：

假设 Mocha 还剩 $k$ 个数据包没有发送，她可以选择 $i \in [1,k]$ 个数据包将其发送，并花费 $F_{n-i+1}$ 的代价，其中 $F_{i}$ 表示斐波那契数列第 $i$ 项的值。每个被发送的数据包有 $\dfrac{p}{q}$ 的概率发送成功，且每个数据包是否发送成功相互独立。发送失败的数据包视为没有发送，需要在接下来继续发送它。

斐波那契数列的定义如下：

$F_i = \begin{cases} 0, &i = 0 \\ 1, &i = 1 \\ F_{i-1}+F_{i-2}, &i \ge 2 \end{cases}$

Mocha 想最小化发送数据包所花费的代价，她想请你帮她算算，如果采取最优策略，将所有数据包全部发送的期望代价是多少。

仅有一行，三个正整数  () 和  (，)，表示 Mocha 需要发送数据包的数量，以及每个数据包发送成功概率的分子和分母。

一个正整数，表示在最优策略下将所有数据包全部发送的期望代价对  取模的结果。

示例1

复制

1 7 10

复制

570425346

只有一个物品，每次发送花费代价为 ，容易得到期望代价为 。

示例2

复制

3 7 10

复制

723843564