1/* ***********************************************
  2Author :111qqz
  3Created Time :2017年10月10日 星期二 17时38分11秒
  4File Name :5950.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define PB push_back
 20#define fst first
 21#define sec second
 22#define lson l,m,rt<<1
 23#define rson m+1,r,rt<<1|1
 24#define ms(a,x) memset(a,x,sizeof(a))
 25typedef long long LL;
 26#define pi pair < int ,int >
 27#define MP make_pair
 28
 29using namespace std;
 30const double eps = 1E-8;
 31const int dx4[4]={1,0,0,-1};
 32const int dy4[4]={0,-1,1,0};
 33const int inf = 0x3f3f3f3f;
 34const int N=7;
 35const LL MOD =2147493647LL;
 36LL a,b,n;
 37struct Mat
 38{
 39    LL mat[N][N];
 40    void clear()
 41    {
 42    ms(mat,0);
 43    }
 44    void print()
 45    {
 46    for ( int i = 0 ; i < N; i++)
 47        for ( int j = 0 ; j < N ; j++)
 48        printf("%lld%c",mat[i][j],j==N-1?'\n':' ');
 49    puts("");
 50    }
 51}M,M1;
 52Mat operator * (Mat a,Mat b)
 53{
 54    Mat c;
 55    c.clear();
 56    for ( int i = 0 ; i < N ; i++)
 57    for ( int j = 0 ; j < N  ; j++)
 58        for ( int k = 0 ; k < N  ; k++)
 59        c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]%MOD)%MOD;
 60    return c;
 61}
 62Mat operator ^ (Mat a,LL b)
 63{
 64    Mat res;
 65    res.clear();
 66    for ( int i = 0 ; i < N ; i++) res.mat[i][i] = 1;
 67    while (b>0)
 68    {
 69    if (b&1) res = res * a;
 70    b = b >> 1LL;
 71    a = a * a;
 72    }
 73    return res;
 74}
 75LL solve()
 76{
 77    M.clear();
 78    M.mat[0][1]=M.mat[1][2]=1;
 79    for ( int i = 1 ; i < N; i++) M.mat[i][N-1]=1,M.mat[i][i]=1;
 80    M.mat[1][0]=M.mat[4][5]=2;
 81    M.mat[1][3]=M.mat[1][5]=M.mat[2][3]=M.mat[2][5]=4;
 82    M.mat[1][4]=M.mat[2][4]=6;
 83    M.mat[3][4]=M.mat[3][5]=3;
 84    //M.print();
 85    M1.clear();
 86    M1.mat[0][0]=a;
 87    M1.mat[1][0]=b;
 88    //注意下标是从1开始的
 89    M1.mat[2][0]=16;
 90    M1.mat[3][0]=8;
 91    M1.mat[4][0]=4;
 92    M1.mat[5][0]=2;
 93    M1.mat[6][0]=1;
 94    //M1.print();
 95    Mat ans;
 96    ans.clear();
 97    ans = (M^(n-2))*M1;
 98    //ans.print();
 99    return ans.mat[1][0];
100}
101
102int main()
103{
104    #ifndef  ONLINE_JUDGE 
105    freopen("./in.txt","r",stdin);
106  #endif
107    int T;
108    cin>>T;
109    while (T--)
110    {
111        scanf("%lld%lld%lld",&n,&a,&b);
112        LL ans = solve();
113        printf("%lld\n",ans);
114    }
115
116
117  #ifndef ONLINE_JUDGE  
118  fclose(stdin);
119  #endif
120    return 0;
121}