Farmer John like to play mathematics games with his $N$ cows. Recently, they are attracted by recursive sequence. In each turn, the cows would stand in a line, while John write two positive numbers $a$ and $b$ on a blackboard. And then, the cows would say their identity number one by one. The first cow says $a$ and the second says $b$. After that, the $i$-th cow says the sum of twice as the second last number, the last number, and $i^4$.

Now, you need to write a program to calculate the number of the $N$-th cow in order to check if John's cows can make it right.

Input format

The first line of input contains an integer $t$, the number of test cases. $t$ test cases follow.

Each case contains only one line with three numbers $N$, $a$ and $b$ ($N, a, b < 2^{31}$) as described above.

Output format

For each test case, output the number of the $N$-th cow. This number might be very large, so you need to output it modulo $2147493647$.

Sample input:

2
3 1 2
4 1 10

Sample output:

85
369

Sample explanation

In the first case, the third number is $85 = 2 * 1 + 2 + 3^4$.

In the second case, the third number is $93 = 2 * 1 + 1 * 10 + 3^4$ and the fourth number is $369 = 2 * 10 + 93 + 4^4$.