题目描述

考虑以下定义在非负整数 $n$ 上的递归关系：

$F(n)=\begin{cases}f_0,& n=0\\f_1,&n=1\\a\times F(n-1)+b\times F(n-2),& otherwise\end{cases}$

其中 $a$、$b$ 是满足以下两个条件的常数：

• $a^2+4b>0$
• $|a-\sqrt{a^2+4b}| \le 2$

给定 $f_0,f_1,a$，$b$ 和 $n$，请你写一个程序计算 $F(n)$，可以假定 $F(n)$ 是绝对值不超过 $10^9$ 的整数（四舍五入）。

输入格式

输入文件一行依次给出 $5$ 个数 $f_0,f_1,a,b$ 和 $n,f_0,f_1$ 是绝对值不超过 $10^9$，$n$ 是非负整数，不超过 $10^9$。另外， $a,b$ 是满足上述条件的实数，且 $|a|,|b|≤10^6$。

输出格式

输出一行一个数，即 $F(n)$。

0 1 1 1 20
0 1-1 0 1000000000
-1 1 4 -3 18

6765
-1
387420487

提示

$F(n)=\frac{k^n(f_1-mf_0)-m^n(f_1-kf_0)}{k-m}$

其中：$m,k=\frac{a\pm \sqrt{a^2+4b}}{2}$

数据范围

• $0<n \le 10^9$
• $|f_0,f_1| \le 10^9$
• $a,b$ 为实数，且 $|a,b|\le 10^6$