#include <bits/stdc++.h>

using namespace std;

const int MAXN = (int) 1e6 + 5;
const int LEN = 10;
const int mod = (int) 1e9 + 7;

int N, B, C;
vector<vector<int> > data;

void rec(int idx, vector<int> v, int limit, int cnt) {
  if (idx == cnt) {
    data.push_back(v);
  } else {
    for (int ones = 0; ones < limit; ones++) {
      v.push_back(ones);
      rec(idx + 1, v, limit, cnt);
      v.pop_back();
    }
  }
}

int add(int a, int b) {
  int ans = (a + b) % mod;
  if (ans >= mod) {
    ans -= mod;
  }
  return ans;
}

int sub(int a, int b) {
  int ans = (a - b) % mod;
  if (ans < 0) {
    ans += mod;
  }
  return ans;
}

int mul(int a, int b) {
  return a * (long long) b % mod;
}

int modpow(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) {
      res = res * (long long) a % mod;
    }
    a = a * (long long) a % mod;
    b >>= 1;
  }
  return res;
}

int gen() {
  data.clear();
  rec(0, vector<int>(), 3, LEN);
  cerr << "N " << N << " " << B << endl;
  map<int, int> mp;
  // data contains all 3^LEN arrays each containing numbers 0, 1 or 2.
  for (auto v: data) {
    int beauty = 0;
    int total_cnt = 1;
    for (int i = 0; i < LEN; i++) {
      int cnt = 0;
      int cur_beauty = 0;
      if (v[i] == 0) {
        cur_beauty = 0;
        cnt = 1;
      } else if (v[i] == 1) {
        cnt = N;
        if (N == 1) {
          cur_beauty = 1;
        } else {
          cur_beauty = mul(N + 1, modpow(2, N - 2));
        }
      } else if (v[i] == 2 && N >= 2) {
        cnt = modpow(2, N);
        cnt = sub(cnt, 1);
        cnt = sub(cnt, N);
        cur_beauty = mul(N, modpow(2, N - 2));
      }
      beauty = add(beauty, beauty);
      beauty = add(beauty, cur_beauty);
      total_cnt = mul(total_cnt, cnt);
    }
    mp[beauty] = add(mp[beauty], total_cnt);
  }
  int ans = 0;
  for (auto it: mp) {
    int beauty = it.first;
    int rev_beauty = mul(beauty, modpow(2, LEN));
    rev_beauty = sub(B, rev_beauty);
    if (mp.find(rev_beauty) != mp.end()) {
      ans = add(ans, mul(mp[beauty], mp[rev_beauty]));
    }
  }
  return ans;
}

int bruteforce(vector<int> v) {
  assert(v.size() == N);
  int ans = 0;
  for (int mask = 0; mask < (1 << N); mask++) {
    int val = 0, len = 0;
    for (int i = 0; i < N; i++) {
      if (mask & (1 << i)) {
        val ^= v[i];
        len++;
      }
    }
    ans += val * len;
    ans %= mod;
  }
  return ans;
}

void testIt() {
  for (N = 3; N <= 50; N++) {
    data.clear();
    rec(0, vector<int>(), 1<<(LEN + LEN), N);
    map<int, int> mp; 
    for (auto v: data) {
      int b = bruteforce(v); 
      mp[b]++;
    }
    cout << "computed " << endl;
    for (auto it: mp) {
      int b = it.first;
      int brute_ans = mp[b];
      B = b;
      int fast_ans = gen();
      printf("bans = %d, fans = %d\n", brute_ans, fast_ans); 
      assert(brute_ans == fast_ans);
    }
  }
}

int main() {
	// This is for testing program's output with a bruteforce solution.
	// testIt();
	
	int T;
	scanf("%d", &T);
	assert(T >= 1 && T <= 10);
	while (T--) {
		scanf("%d %d %d", &N, &B, &C);
		assert(N >= 1 && N <= (int) 1e6);
		assert(B >= 1 && B < mod);
		assert(C == (1 << 20));
		int ans = gen();
		printf("%d\n", ans); 
  }
  return 0;
}