"A fight? Count me in!" 要打架了，算我一个。

"Everyone, get in here!" 所有人，都过来！

冷酷的酒客（Grim Patron）对战歌指挥官（Warsong Commander）的削弱感到很伤心，他打算用一道数学题来纪念战歌指挥官。

设$ \left \{ u_i \right \} $ 为一数列

\begin{equation} u_i = a + \frac{b}{u_{i-1}} + \frac{c}{u_{i-1}u_{i-2}} \quad (i \geq 2) \end{equation}

已知 $u_0, u_1, a, b, c, n$。保证 $x^3 = a x^2 + b x + c$ 有 $3$ 个不同的正整数解。

求 $u_n$。

输入格式

输入仅一行，包含 $6$ 个整数 $u_0, u_1, a, b, c, n$。

输出格式

输出仅一行，包含 $1$ 个整数，保留至少8位至多15位小数。如果你的答案和我们的答案差别不超过 $10^{-6}$，则认为正确。考虑到浮点运算本身的误差，当你的答案与真实答案差别不超过 $10^{-6} - 10^{-8}$ 时，才能保证正确。

-7 29 31 -311 1001 100

11.00000000

限制与约定

对于 100% 的数据，$c \leq 100000$，$ \lvert u_0 \rvert \leq 1000, \lvert u_1 \rvert \leq 1000 $，$0 \leq n \leq 10^9 $。

对于 40% 的数据，$ n \leq 20 $。

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

关于浮点误差

你可以不用理会这段话。

浮点数由于是使用有效数字的方式进行的存储，因此大多数的小数从读入的一刻起就已经产生了误差。判定绝对误差的减法运算在两个数的指数不同时也会在末尾处产生截断误差。

我们设参考答案与判断的过程中产生的误差为 $\delta_1$。在大多数情况下，我们只能认为这个值是随机变量，能估计出这个值的上限 $\epsilon_1$。例如在本题中，我们能证明 $\epsilon_1 \leq 10^{-8}$，即 $\left | \delta_1 \right | \leq 10^{-8}$。

设希望容忍的误差范围是 $\epsilon_2$，也就是实际中我们用来判断相等的参数，在本题中为 $\epsilon_2 = 10^{-6}$。如果你的答案与真实的答案差的绝对值不超过 $\epsilon_2 - \epsilon_1$，那么我们能保证你能得分。如果你的答案与真实的答案差的绝对值了超过 $\epsilon_2 + \epsilon_1$，那么你一定不能得分。但如果在两个值之间，我们不知道你能不能得分，只能祈求机器产生的误差和你的差异接近才有可能得分。

下载

样例数据下载