#include <bits/stdc++.h>

using namespace std;

const int MOD = (int) 1e9 + 7;

__int128 calc(long long n, long long a, long long b) {
    __int128 res = (__int128) n * n * n * b + (__int128) (n - 1) * n * n * a;
    if (n == 1) {
        return res;
    }
    res = min(res, (__int128) 18 * (n / 2) * (n / 2) * a + 7 * calc(n / 2, a, b));
    return res;
}

int main() {
    int case_cnt; cin >> case_cnt;
    while (case_cnt--) {
        long long n, a, b;
        
        cin >> n >> a >> b;
        
        cout << (long long) (calc(n, a, b) % MOD) << endl;
    }
    
    return 0;
}