题目描述

一个数列 $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$。