高数Umaru系列(10)——简单题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

题目描述很简单,已知递推式F(n)=a*F(n-1)+b*F(n-2),给定a,b,F(0),F(1)的值以及n,求F(n)。

(其中1 < = a,b,F(0),F(1) < = 10,0 < = n < = 10^9)

Input

 多组输入。

对于每组输入,只有一行五个整数,分别是a,b,F(0),F(1),n,含义及范围如题目描述

Output

 对于每组输入,输出一个F(n),结果可能会比较大,需要对1000000007取余,即求F(n)%1000000007,每组输出占一行

Sample Input

1 1 0 1 4
2 3 2 3 6

Sample Output

3
912

Hint

 

Source

Shannon