#include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const LL mod = ;

 const int maxn = ;

 LL n, a, b;

 typedef struct Matrix {

     LL m[maxn][maxn];

     int r;

     int c;

     Matrix() {

         r = c = ;

         memset(m, , sizeof(m));

     }

 } Matrix;

 Matrix mul(Matrix m1, Matrix m2) {

     Matrix ans = Matrix();

     ans.r = m1.r;

     ans.c = m2.c;

     for(int i = ; i <= m1.r; i++) {

         for(int j = ; j <= m2.r; j++) {

                for(int k = ; k <= m2.c; k++) {

                 if(m2.m[j][k] == ) continue;

                 ans.m[i][k] = ((ans.m[i][k] + m1.m[i][j] * m2.m[j][k] % mod) % mod) % mod;

             }

         }

     }

     return ans;

 }

 Matrix quickmul(Matrix m, LL n) {

     Matrix ans = Matrix();

     for(int i = ; i <= m.r; i++) {

         ans.m[i][i]  = ;

     }

     ans.r = m.r;

     ans.c = m.c;

     while(n) {

         if(n & ) {

             ans = mul(m, ans);

         }

         m = mul(m, m);

         n >>= ;

     }

     return ans;

 }

 int main() {

     // freopen("in", "r", stdin);

     int T;

     scanf("%d", &T);

     while(T--) {

         scanf("%I64d%I64d%I64d",&n,&a,&b);

         if(n == ) {

             printf("%I64d\n", a);

             continue;

         }

         if(n == ) {

             printf("%I64d\n", b);

             continue;

         }

         Matrix x; x.r = , x.c = ;

         Matrix y; y.r = , y.c = ;

         x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=;

         x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=;

         x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=;

         x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=;

         x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=;

         x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=;

         x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=,x.m[][]=;

         y.m[][]=b,y.m[][]=a,y.m[][]=,y.m[][]=,y.m[][]=,y.m[][]=,y.m[][]=;

         Matrix p = quickmul(x,n-);

         Matrix ret = mul(p,y);

         printf("%I64d\n", ret.m[][]);

         // cout << ret.r << " " << ret.c << endl;

     }

     return ;

 }