#include<bits/stdc++.h>
using namespace std;
using LL=long long;
using ll=__int128;

const int mo=1e9+7;
LL qpow(LL a,LL b)
{
    LL ans=1;
    a%=mo;
    while(b)
    {
        if(b&1)
            ans=ans*a%mo;
        b>>=1;
        a=a*a%mo;
    }
    return ans;
}
//--------------------------------

ll ans1;
ll ans;

ll dfs(LL n,LL a,LL b)
{
    ll tep=(ll)n*n*n*b+(ll)(n-1)*n*n*a;
    if(n&1)
        return tep;
    return min(tep,(ll)18*(n/2)*(n/2)*a+7*dfs(n/2,a,b));
        
}

int main()
{
    int T;
    scanf("%d",&T);
    LL n,a,b;
    
    while(T--)
    {
        cin>>n>>a>>b;
        ans1=(ll)n*n*n*b+(ll)(n-1)*n*n*a;
        if(n&1)
        {
            printf("%lld\n",(LL)(ans1%mo));
        }    
        else
        {
            ans=dfs(n,a,b);
            printf("%lld\n",(LL)(ans%mo));
        }    
    }    
    return 0;    
}