#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;

#define mod 1000000007
#define ll unsigned __int128

int T;
ll n, a, b;

ll dfs (ll now){
    ll fi = now * now * now * b;
    ll se = (now - 1) * now * now * a;
    ll ans1 = (fi + se);
    if (now % 2 == 1)
        return ans1;
    ll ans = dfs (now / 2);
    fi = 18 * (now / 2) * (now / 2) * a;
    se = ans * 7;
    ll ans2 = (fi + se);
    return min (ans1, ans2);
}
int main (){
    scanf ("%d", &T);
    while (T --){
        scanf ("%I64d %I64d %I64d", &n, &a, &b);
        long long ans = dfs (n) % mod;
        printf ("%I64d\n", ans);
    }
    return 0;
}