题目描述

考虑以下定义在非负整数$\red{n}$上的递归关系:

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

其中$\red{a}$、$\red{b}$是满足以下两个条件的常数:

$\red{(1) a^2+4b>0}$

$\red{(2) |a-\sqrt{a^2+4b}|≤}$$\red{2}$

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

输入格式

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

输出格式

输出一行一个数,即$\red{F(n)}$。

样例

输入样例1

0 1 1 1 20

输出样例1

6765

输入样例2

0 1 -1 0 1000000000

输出样例2

-1

输入样例3

-1 1 4 -3 18

输出样例3

387420487