题目描述

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

$ F(n)=\begin{cases}f_0,& n=0\\f_1,&n=1\\a*F(n-1)+b*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$

来源

• 信息学奥赛之数学一本通
• stong9070整理