#include <cstdio>
#include <iostream>

#define Int register int
#define uLL unsigned __int128


const uLL MOD = 1e9 + 7;

inline uLL Calcul ( const uLL n, const uLL a, const uLL b ) {
    uLL Ans1 = ( n * n * n * b + ( n - 1 ) * n * n * a );
    if ( n & 1 ) return Ans1;
    uLL Ans2 = ( 18 * ( n / 2 ) * ( n / 2 ) * a + 7 * Calcul ( n / 2, a, b ) );
    return Ans1 < Ans2 ? Ans1 : Ans2;
}


inline void Work () {
    int T;
    scanf ( "%d", &T );
    while ( T -- ) {
        long long a, b, n;
        scanf ( "%I64d %I64d %I64d", &n, &a, &b );
        printf ( "%I64d\n", ( long long )( Calcul ( 1llu * n, a, b ) % MOD ) );
    }
}

int main () {
    Work ();
    return 0;
}