A38691.奇怪の公式

不会出题了，整点古希腊公式吧……？

NH 又开始邪恶的出题计划了！这次他想不到用什么情境了，于是 NH 求助了 FM，以下为我们截取的部分对话

NH： 你说如果我让他们求以下 $f_{n,x,y}$ 的值行不行。

$$f_{n,x,y}=(\sum_{0 \le i,2|i}^{n}C_n^i + \sum_{i=0}^{n}(\sum_{j=0}^{n}y^jx^{n-j}C_n^j)C_n^i)\bmod (10^9+7)$$

FM：这也太简单了吧，完全不是 T6 的难度。

NH：也对，这种题目放在 T6 完全不能造福玩家，真的是太难受了。

……

NH：欸，我有一计，我们可以再设 $g_i$ 为：

$$g_i = \begin{cases} [i = 1] & (i \leq 1) \\ (f_{x,n,x+y}g_{i - 1} + f_{y,x+y,n}g_{i - 2})& (i \gt 1) \end{cases}$$

然后让他们求 $\gcd{(g_n,g_{x+y})}$ ，这样就能造福更多玩家了。

FM：确实有点难度了，不过这不就是个平衡博弈树模板题吗，网上搜一搜就有，真的是太难受了。

NH 和 FM 沉思了一会……

FM：欸，我有一计，NH，我觉得我们可以定义 $h(x)$ 如下：

$$h(x)=\sum_{d=1,x|d}^{x} k^2(k=1)$$

让他们求 $h((\gcd{(g_n,g_{x+y}) \mod 10^5})!)$ 怎么样？

NH：我倒是觉得那个 $h(x)$ 每次加的只是一个单一定值，你让玩家代码做如此重复的事情，就违背了我们造福玩家的宗旨。

FM：emmm……，让我再思考一下……

……

NH：欸，我又有一计，既然定量不能造福玩家，那么我们不妨改写 $h(x)$ 为：

$$h(x)=\sum_{d=1,x|d}^{x}p\sum_{1 \le i}^{\infty}i \times p(1-p)^i(0 < p <1)$$

再让他们求 $h((\gcd{(g_n,g_{x+y})} \bmod 10^5)!)$ ，这样就能最大程度的造福玩家了

FM：这个好这个好，就定这一版了！

NH & FM：可是，代码怎么写呢……

于是，FM 与 NH 一起找到了你，希望你帮忙把这题的代码出了，顺便把这题 AC 了。

输入共 $1$ 行 $3$ 个正整数 $n,x,y$ 和一个两位实数 $p$，表示四个参数。

输出 $1$ 行 $1$ 个整数，表示 $h((\gcd{(g_n,g_{x+y})} \bmod 10^5)!)$ 的值。

【数据范围】

对于所有数据，保证：

$1 \le n,x,y \le 10^{12}$，$0<p<1$，$p=0.01k(k \in N^+)$，最后答案在 long long 的范围内

本题测试点等分。

【样例解释】

样例组 #1：当 $n=3,x=1,y=1$ 时，

$$g_n=g_3=f_{1,3,2}g_2+f_{1,2,3}g_1=f_{1,3,2}^2g_1+f_{1,3,2}f_{1,2,3}g_0+f_{1,3,2}g_1=f_{1,3,2}^2+f_{1,2,3}f_{1,2,3}+f_{1,2,3}$$

$$f_{1,3,2}=(\sum_{0 \le i,2|i}^{1}C_1^i + \sum_{i=0}^{1}(\sum_{j=0}^{1}3^j2^{1-j}C_1^j)C_1^i)\bmod 10^9+7=(1+10) \bmod 10^9+7=11$$

$$f_{1,2,3}=(\sum_{0 \le i,2|i}^{1}C_1^i + \sum_{i=0}^{1}(\sum_{j=0}^{1}2^j3^{1-j}C_1^j)C_1^i)\bmod 10^9+7=(1+10) \bmod 10^9+7=11$$

$$g_n=f_{1,3,2}^2+f_{1,3,2}f_{1,2,3}+f_{1,2,3}=253,g_{x+y}=g_2=242$$

$$\gcd{(g_n,g_{x+y})} \bmod 10^5=\gcd{(253,242)} \bmod 10^5=11$$

$$h((\gcd{(g_n,g_{x+y})} \bmod 10^5)!)=h(11!)=184202887$$