#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const long long mod=1e9+7;
typedef __int128 Int128;
int scan(Int128 &x){
    x=0;
    int sgn=1;
    char ch;
    while(ch=getchar()){
        if(ch==EOF) return EOF;
        else if(ch=='-') sgn=-sgn;
        else if(ch>='0' && ch<='9'){ x=x*10+(ch-'0'); break; }
    }
    while((ch=getchar())>='0' && ch<='9'){
        x=x*10+(ch-'0');
    }
    x*=sgn;
    return 1;
}

void _print(Int128 x){
    if(x>9) _print(x/10);
    putchar(x%10+'0');
}

void print(Int128 x){
    if(x<0){ x=-x; putchar('-'); }
    _print(x);
}

Int128 n,a,b;
Int128 f(Int128 x){
    if(x==0) return 0;
    if(x==1) return b;
    Int128 f1 = x*x*x*b + (x-1)*x*x*a;
    if(x%2==1) return f1;
    Int128 f2 = 9*x*x/2*a + 7*f(x/2);
    return min(f1,f2);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scan(n);
        scan(a);
        scan(b);
        print(f(n)%mod);
        printf("\n");
    }
    return 0;
}