#include <cstdio>
#include <cstdlib>
#include <map>
#include <algorithm>

using namespace std;

int T, a, b;
long long n;

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

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