#include <bits/stdc++.h>
using namespace std;
const int max_n = 3e5 + 5;
const int mod = 1e9 + 7;
int maska[35];
int maska2[35];
int rob2(int a, int b, int k) {
  if (b < a) return rob2(b, a, k);
  int ans = 0;
  for (int i = (0); i < (30); ++i) {
    if (!(a & (1 << i))) continue;
    for (int j = (0); j < (30); ++j) {
      if (!(b & (1 << j))) continue;
      int dowolnych = max(i, j);
      int pocz = ((a ^ (1 << i)) & maska2[dowolnych]) ^
                 ((b ^ (1 << j)) & maska2[dowolnych]);
      pocz = pocz & maska2[dowolnych];
      int mam = 1 << min(i, j);
      if (pocz < (k & maska2[dowolnych])) {
        int kutas = ((1 << dowolnych) * 1LL * mam) % mod;
        ans += (kutas * 1LL * pocz) % mod;
        ans %= mod;
        kutas =
            ((((1 << (dowolnych)) * 1LL * ((1 << dowolnych) - 1))) / 2) % mod;
        ans += (kutas * 1LL * mam) % mod;
        ans %= mod;
        ans += ((1 << dowolnych) * 1LL * mam) % mod;
        ans %= mod;
      } else {
        if ((k & maska2[dowolnych]) == pocz) {
          int reszta = k & maska[dowolnych];
          int kutas = ((reszta + 1) * 1LL * mam) % mod;
          ans += (kutas * 1LL * pocz) % mod;
          ans %= mod;
          kutas = ((reszta * 1LL * (reszta + 1)) / 2) % mod;
          ans += (kutas * 1LL * mam) % mod;
          ans %= mod;
          ans += ((reszta + 1) * 1LL * mam) % mod;
          ans %= mod;
        }
      }
    }
  }
  return ans;
}
int rob(int a, int b, int k) {
  if (a == 0 || b == 0) return 0;
  return rob2(a, b, k - 1);
}
int main() {
  maska[0] = 0;
  for (int i = (1); i < (32); ++i) maska[i] = maska[i - 1] + (1 << (i - 1));
  for (int i = (0); i < (31); ++i) maska2[i] = maska[i] ^ maska[31];
  int(q);
  scanf("%d", &(q));
  ;
  while (q--) {
    int(x1), (y1);
    scanf("%d%d", &(x1), &(y1));
    ;
    int(x2), (y2);
    scanf("%d%d", &(x2), &(y2));
    ;
    int(k);
    scanf("%d", &(k));
    ;
    int ans1 = (rob(x2, y2, k) + rob(x1 - 1, y1 - 1, k)) % mod;
    int ans2 = (rob(x1 - 1, y2, k) + rob(x2, y1 - 1, k)) % mod;
    if (ans1 < 0) ans1 += mod;
    printf("%d\n", (ans1 + mod - ans2) % mod);
  }
}
