Problem Description

Farmer John likes to play mathematics games with his N cows. Recently, they are attracted by recursive sequences. In each turn, the cows would stand in a line, while John writes 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 the first number a and the second says the second number b. After that, the i-th cow says the sum of twice the (i-2)-th number, the (i-1)-th number, and i4. 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

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 where N,a,b < 231 as described above.

 

Output

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

#pragma comment(linker, "/STACK:102400000,102400000")

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <map>

#include <set>

#include <ctime>

#include <queue> 

#define LL long long

using namespace std;

const LL _MOD = , maxN = , MOD = _MOD*;

int n;

LL f(int _n)

{

    LL n = _n, ans =, t=;

    t = t*n%MOD; ans = (ans + t*)%MOD;

    t = t*n%MOD; ans = (ans + t*)%MOD;

    t = t*n%MOD; ans = (ans + t*)%MOD;

    t = t*n%MOD; ans = (ans + t)%MOD;

    return ans/ % _MOD;

}

struct matrix

{

    int n, m;

    LL a[maxN][maxN];

    LL* operator [](int x) {return a[x];}

    void print()

    {

        for(int i = ; i <= n; i++)

        {

            for(int j = ; j <= m; j++)

                printf("%d ", a[i][j]);

            printf("\n");

        }

        printf("\n");

    }

};

matrix operator *(matrix a, matrix b)

{

    matrix c; c.n = a.n; c.m = b.m;

    memset(c.a, , sizeof(c.a));

    LL tmp;

    for(int i = ; i <= a.n; i++)

    {

        tmp = ;

        for(int j = ; j <= b.m; j++)

        {

            for(int k = ; k <= a.m; k++)    tmp = (tmp+a[i][k] * b[k][j])%_MOD;

            c[i][j] = tmp % _MOD;

            tmp = ;

        }

    }

    return c;

}

matrix operator ^(matrix a, LL x)

{

    matrix b;

    memset(b.a, , sizeof(b.a));

    b.n = a.n; b.m = a.m;

    for(int i=; i <= a.n; i++)    b[i][i]=;

    for(;x;a=a*a,x>>=)    if(x&)    b=b*a;

    return b;

}

int main()

{

//    cout<<2*f(3)+f(4)-f(5)<<endl;

//    return 0;

    #ifndef ONLINE_JUDGE

    freopen("test_in.txt", "r", stdin);

    //freopen("test_out.txt", "w", stdout);

    #endif

    int T; scanf("%d", &T);

    while(T--)

    {

        int a, b, n; scanf("%d%d%d", &n, &a, &b);

        LL _a = a; _a += f(); LL _b = b; _b += f();

        matrix m; m.n = m.m = ; m[][] = _a; m[][] = _b; m[][] = m[][] = ;

        matrix t; t.n = t.m = ; t[][] = ; t[][] = ;  t[][] = t[][] = ;

        t = t^(n-);

        m = m*t;

        LL ans = (m[][] - f(n) + _MOD) % _MOD;

        printf("%d\n", (int)ans);

    }

}