#include <iostream>

long long MOD = 1000000007;

long long Calc1(long long n, long long a, long long b, long long mod) {
    return (n * n % mod * n % mod * b % mod + (n - 1) * n % mod * n % mod * a % mod) % mod;
}

long long Calc2(long long n, long long a, long long b, long long mod) {
    long long n2 = n >> 1;
    return (18 * n2 % mod * n2 % mod * a % mod 
        + 7 * n2 % mod * n2 % mod * n2 % mod * b % mod
        + 7 * (n2 - 1) % mod * n2 % mod * n2 % mod * a % mod) % mod;
}

long long LONG_LONG_MOD = MOD * MOD;

long long Cost(long long n, long long a, long long b) {
    if (n <= 30) {
        if (n & 1) {
            return Calc1(n, a, b, LONG_LONG_MOD);
        } else {
            long long cost1 = Calc1(n, a, b, LONG_LONG_MOD);
            long long n2 = n >> 1;
            long long cost2 = 18 * n2 * n2 * a + 7 * Cost(n2, a, b);
            return std::min(cost1, cost2);
        }
    } else {
        if (n & 1) {
            return Calc1(n, a, b, MOD);
        } else {
            long long n2 = n >> 1;
            long long cost = (18 * n2 % MOD * n2 % MOD * a % MOD + 7 * Cost(n2, a, b) % MOD) % MOD;
            return cost;
        } 
    }
}

int main() {
    int T;
    std::cin >> T;
    for (int ca = 1; ca <= T; ++ ca) {
        long long n, a, b;
        std::cin >> n >> a >> b;
        std::cout << Cost(n, a, b) % MOD << std::endl;
    }
    return 0;
}