[NOIP2006-普及] 数列

题目背景

题解：https://blog.csdn.net/kkkksc03/article/details/85008130

题目描述

一个数列$a_n$，已知$a_1$及$a_2$两项。

数列$a_n$满足递推式$a_n=x \times a_{n-1}+ y \times a_{n-2}(n\geq 3).$

求

由于答案可能过大，对$10^9+7$取模。

输入输出格式

输入格式：

第一行一个整数$T$，即数据组数。

下面$T$行，每行$5$个整数，$n,a_1,a_2,x,y$，含义如上。

输出格式：

共$T$行，每行一个整数，即为每组数据的答案。

输入输出样例

输入样例#1：

3 5 1 1 1 1 4 3 4 3 2 461564597527246 987489553 321654648 164165256 315648984

输出样例#1：

40 4193 480929868

说明

样例解释：

对于第一组样例，可知数列为$1,1,2,3,5$，则答案是$1^2+1^2+2^2+3^2+5^2=40$。

对于第二组样例，可知数列为$3,4,18,62$，则答案是$3^2+4^2+18^2+62^2=4193$。

第三组样例不予解释。

对于前20%的数据，保证$x=y=1$。

对于100%的数据，$T=30000,1\le n \le 10^{18},1\le a_1,a_2 ,x,y \le 10^9$。