#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define debug(x) cerr<<#x<<" = "<<(x)<<endl
#define eps 1e-8
#define pi acos(-1.0)
using namespace std;
void test(){cerr<<"\n";}
template<typename T,typename... Args>void test(T x,Args... args){cerr<<x<<" ";test(args...);}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MAXN=(int)3e5+5;
const int MOD=(int)1e9+7;
ll a,b;
ll f(ll n){
    n%=MOD;
    return (n*n%MOD*n%MOD*b%MOD+(n+MOD-1)*n%MOD*n%MOD*a%MOD)%MOD;
}
ll gao(ll n){
    if(n<=100){
        if(n&1)return (n*n*n*b+(n-1)*n*n*a);
        else {
            ll tmp=n*n*n*b+(n-1)*n*n*a;
            n/=2;
            ll t2=18*n*n*a+gao(n)*7;
            return min(t2,tmp);
        }
    }
    else {
        if(n&1)return f(n);
        else {
            ll res=gao(n/2)%MOD*7%MOD;
            n/=2;
            res=res+18*n%MOD*n%MOD*a;
            res%=MOD;
            return res;
        }

    }
}
int main()
{
    ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n>>a>>b;
        cout<<gao(n)%MOD<<"\n";
    }
    return 0;
}