题目描述
一个数列an,已知a1及a2两项。
数列an满足递推式an=x×an−1+y×an−2(n≥3).
求$$\sum_{i=1}^na_i^2.$$
由于答案可能过大,对109+7取模。
输入格式
第一行一个整数T,即数据组数。
下面T行,每行5个整数,n,a1,a2,x,y,含义如上。
输出格式
共T行,每行一个整数,即为每组数据的答案。
样例
3
5 1 1 1 1
4 3 4 3 2
461564597527246 987489553 321654648 164165256 315648984
40
4193
480929868
说明
样例解释:
对于第一组样例,可知数列为1,1,2,3,5,则答案是12+12+22+32+52=40。
对于第二组样例,可知数列为3,4,18,62,则答案是32+42+182+622=4193。
第三组样例不予解释。
对于前20%的数据,保证x=y=1。
对于100%的数据,T=30000,1≤n≤1018,1≤a1,a2,x,y≤109。