#include <bits/stdc++.h>
#define MOD 1000000007

using namespace std;

typedef long long ll;
typedef __int128 lll;

lll calc(ll n,ll a,ll b) {
  if (n&1) return (lll)(n-1)*n*n*a+(lll)n*n*n*b;
  else return min((lll)(n-1)*n*n*a+(lll)n*n*n*b,(lll)18*(n/2)*(n/2)*a+7LL*calc(n/2,a,b));
}

int main() {
  int cases;
  scanf("%d",&cases);
  for(;cases;cases--) {
      ll n,a,b;
      scanf("%I64d%I64d%I64d",&n,&a,&b);
      printf("%I64d\n",(ll)(calc(n,a,b)%MOD));
  }
  return 0;
}