1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <algorithm>
 6 #include <cmath>
 7 #include <vector>
 8 #include <queue>
 9 #include <map>
10 #include <stack>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 #define ms(a, b) memset(a, b, sizeof(a))
15 #define pb push_back
16 #define mp make_pair
17 const int INF = 0x7fffffff;
18 const int inf = 0x3f3f3f3f;
19 const LL mod = 2147493647;
20 const int maxn = 500+10;
21 struct Matrix
22 {
23     LL c[7][7];
24 };
25 Matrix base_Matrix =  {0,2,0,0,0,0,0,
26                        1,1,0,0,0,0,0,
27                        0,1,1,0,0,0,0,
28                        0,4,4,1,0,0,0,
29                        0,6,6,3,1,0,0,
30                        0,4,4,3,2,1,0,
31                        0,1,1,1,1,1,1};
32 Matrix mult(Matrix a, Matrix b)
33 {
34     Matrix hh = {0};
35     for(int i = 0;i<7;i++)
36         for(int j = 0;j<7;j++)
37             for(int k = 0;k<7;k++){
38                 hh.c[i][j] += (a.c[i][k]*b.c[k][j])%mod;
39                 hh.c[i][j] %= mod;
40             }
41     return hh;
42 }
43 Matrix qpow_Matrix(Matrix a, LL b)
44 {
45     Matrix base = a;
46     Matrix ans;
47     for(int i = 0;i<7;i++)
48         for(int j = 0;j<7;j++)
49             if(i==j)    ans.c[i][j] = 1;
50             else ans.c[i][j] = 0;
51 
52     while(b){
53         if(b&1) ans = mult(ans, base);
54         base = mult(base, base);
55         b>>=1;
56     }
57     return ans;
58 }
59 void init() {
60 
61 }
62 void solve() {
63     LL n, a, b;
64     cin >> n >> a >> b;
65     Matrix begin ={a,b,16,8,4,2,1};
66     if(n==1){
67         cout << a << endl;
68         return;
69     }
70     if(n==2){
71         cout << b << endl;
72         return;
73     }
74     Matrix tmp = qpow_Matrix(base_Matrix, n-2);
75     Matrix ans = mult(begin, tmp);
76 //    for(int i = 0;i<7;i++){
77 //        for(int j = 0;j<7;j++)
78 //            cout << ans.c[i][j] << " ";
79 //        cout << endl;
80 //    }
81 //    cout << endl;
82     cout << ans.c[0][1] << endl;
83 }
84 int main() {
85 #ifdef LOCAL
86     freopen("input.txt", "r", stdin);
87 //        freopen("output.txt", "w", stdout);
88 #endif
89     ios::sync_with_stdio(0);
90     cin.tie(0);
91     int T;
92     cin >> T;
93     while(T--){
94         init();
95         solve();
96     }
97     return 0;
98 }