题目描述

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

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

求$$\sum_{i=1}^na_i^2.$$

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

输入格式

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

下面$T$行，每行$5$个整数，$n,a_1,a_2,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$，则答案是$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$。