You are given two positive functions  $f(n)$ and $g(n)$ defined as follows:

$f(n) = n*g(n-1) + (n-1)*g(n-2) + ... + 2* g(1) + g(0)$

$g(n) = n*f(n-1) + (n-1)*f(n-2) + ... + 2*f(1) + f(0)$

Note: $abs(n-1000000007) \le 10^5$

You will be asked $T$ queries. In each query you will be given three integers $n,f(0) , g(0)$. You need to calculate the value of $(f(n) + g(n) ) \bmod 10^9+7$. 

Input
The first line contains an integer $T$ as input.
The next $T$ lines contain three integers $n,f(0),g(0)$.

Output
In the output, you need to print the value of $(f(n) + g(n) ) \bmod 10^9+7$.

Constraints
$1 \le T \le 10^2\\ 1 \le n \le 10^9\\ 1 \le f(0),g(0) \le 10^{18}$