題目描述

定義一個數列 F ，滿足如下性質：

F₁=a
F₂=b
F_i=F_i-1+F_i-2

其中a,b皆為正整數，i為大於2的正整數。

給定 F 的第 m 項F_m 以及第 n 項 F_n，求 F 的第 k 項 F_k 對 10⁹+7 取模的值。

輸入格式

一行五個整數，分別是 m,F_m ,n,F_n ,k。

一個整數表示答案對10⁹+7 取模的結果。

1 1 3 2 9

數據範圍
對於10% 的數據，n=1,m=2,k≤10；
對於30% 的數據，n,m≤3,F_m ,F_n,k≤100；
對於60% 的數據，n,m≤30,F_m ,F_n,k≤10⁶；
對於100%的數據，1≤n,m≤50,0≤F_m ,F_n≤10¹⁸,1≤k≤10⁹。