数列

• 时间限制：1.5 秒
• 内存限制：64 MiB

题目描述

给定数列 $\{a_n\}$ 的前两项 $a_1,a_2$。对于 $n\ge 3$，数列满足

求

对 $10^9+7$ 取模后的值。

输入格式

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

接下来 $T$ 行，每行五个整数 $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$，平方和为 $40$。

第二组数列的前四项为 $3,4,18,62$，平方和为 $4193$。

数据范围

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

一份输入中各组询问的 $n$ 之和记为 $\sum n$。

本题采用独立测试点计分。