#include<cstdio>
#include<algorithm>
#define mo 1000000007
using namespace std;
int test,a,b;
long long n;
inline long long f(int n,int a,int b){
    if(n==1)return b;
    long long t=f(n/2,a,b);
    return min(1LL*n*n*n*b+1LL*(n-1)*n*n*a,1LL*18*(n/2)*(n/2)*a+t*7); 
}
inline int work(long long n,int a,int b){
    if(n>=1024){
        int t=n/2%mo;
        return (1LL*t*t%mo*18%mo*a%mo+1LL*7*work(n/2,a,b)%mo)%mo;
    }
    return f(n,a,b)%mo;
}
int main(){
    scanf("%d",&test);
    while(test--){
        scanf("%I64d%d%d",&n,&a,&b);
        printf("%d\n",work(n,a,b));
    }
}