Background

Solution: https://blog.csdn.net/kkkksc03/article/details/85008130

Problem Description

Given a sequence $a_n$, where $a_1$ and $a_2$ are known.

The sequence $a_n$ satisfies the recurrence $a_n = x \times a_{n-1} + y \times a_{n-2} \ (n \ge 3).$

Compute $\sum_{i=1}^n a_i^2$.

Since the answer may be very large, output it modulo $10^9+7$.

Input Format

The first line contains an integer $T$, the number of test cases.

The next $T$ lines each contain $5$ integers $n, a_1, a_2, x, y$, with the meanings as described above.

Output Format

Output $T$ lines, each containing one integer, the answer for each test case.

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

40
4193
480929868

Hint

Sample explanation:

For the first sample, the sequence is $1, 1, 2, 3, 5$, so the answer is $1^2 + 1^2 + 2^2 + 3^2 + 5^2 = 40$.

For the second sample, the sequence is $3, 4, 18, 62$, so the answer is $3^2 + 4^2 + 18^2 + 62^2 = 4193$.

The third sample will not be explained.

For the first $20\%$ of the testdata, it is guaranteed that $x = y = 1$.

For $100\%$ of the testdata, $T = 30000$, $1 \le n \le 10^{18}$, $1 \le a_1, a_2, x, y \le 10^9$.

Translated by ChatGPT 5