#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mm=1000000007;

int Tn;

long long n,a,b;

long long g(long long n){
    if(n&1)return n*n*n*b+(n-1)*n*n*a;
    return min(n*n*n*b+(n-1)*n*n*a,18*(n/2)*(n/2)*a+7*g(n/2));
}

long long f(long long n){
    if(n&1){
        return (n*n%mm*n%mm*b+(n-1)*n%mm*n%mm*a)%mm;
    }else if(n>=1000){
        return (18*(n/2)%mm*(n/2)%mm*a%mm+7*f(n/2))%mm;
    }else{
        return min(n*n*n*b+(n-1)*n*n*a,18*(n/2)*(n/2)*a+7*g(n/2))%mm;
    }
}

int main(){
    scanf("%d",&Tn);
    while(Tn--){
        scanf("%lld%lld%lld",&n,&a,&b);
        printf("%lld\n",f(n));
    }
    return 0;
}