B. Subtractonacci
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Fibonacci sequence, where each number is the sum of the two preceding ones, is well-known in mathematics. Consider a sequence $$$a$$$ that follows a similar pattern but with subtraction instead of addition.

Given three integers $$$n$$$, $$$a_1$$$, and $$$a_2$$$. For $$$i \geq 3$$$, $$$a_i = a_{i-1} - a_{i-2}$$$.

Your task is to find

$$$$$$\sum_{i = 1}^{n} a_i \mod (10^9 + 7)$$$$$$

Input

The input begins with a single integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$, the number of test cases.

Each of the next $$$t$$$ lines contains three integers $$$n$$$, $$$a_1$$$, and $$$a_2$$$ $$$(1 \leq n, a_1, a_2 \leq 10^9)$$$.

Output

For each test case, output the answer.

Example
Input
6
3 2 5
4 1 2
1 1 1
3 10 3
799843967 796619138 446173607
1000000000 1000000000 1000000000
Output
10
3
1
6
649554476
1000000000