#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int query, x, xx, y, yy, k;
int mex(int x) { return 1 << (31 - __builtin_clz(x)); }
pair<long long, long long> dfs(int x, int y, int bit) {
  if (bit == 0) return make_pair(0ll, 0ll);
  if (x == 0) return make_pair(0ll, 0ll);
  if (y == 0) return make_pair(0ll, 0ll);
  if (x > y) swap(x, y);
  int z = mex(y);
  int bit1 = min(z, bit);
  long long gas = 0, ans = 0;
  if (z > x) {
    ans = (((long long)bit1 * (bit1 + 1) / 2) % mod) * x % mod;
    gas = (long long)bit1 * x % mod;
    pair<long long, long long> tmp = dfs(x, y - z, max(bit - z, 0));
    ans = (ans + tmp.first + tmp.second * z) % mod;
    gas = (gas + tmp.second) % mod;
  } else {
    ans = (((long long)bit1 * (bit1 + 1) / 2) % mod) * z % mod;
    gas = (long long)bit1 * z % mod;
    pair<long long, long long> tmp = dfs(x - z, y - z, bit);
    ans = (ans + tmp.first) % mod;
    gas = (gas + tmp.second) % mod;
    tmp = dfs(z, y - z, max(bit - z, 0));
    ans = (ans + tmp.first + tmp.second * z) % mod;
    gas = (gas + tmp.second) % mod;
    tmp = dfs(x - z, z, max(bit - z, 0));
    ans = (ans + tmp.first + tmp.second * z) % mod;
    gas = (gas + tmp.second) % mod;
  }
  return make_pair(ans, gas);
}
int main() {
  for (scanf("%d", &query); query--;) {
    scanf("%d %d %d %d %d", &x, &y, &xx, &yy, &k);
    int ans = 0;
    pair<long long, long long> tmp = dfs(xx, yy, k);
    ans = (ans + tmp.first) % mod;
    tmp = dfs(x - 1, y - 1, k);
    ans = (ans + tmp.first) % mod;
    tmp = dfs(x - 1, yy, k);
    ans = (ans + mod - tmp.first) % mod;
    tmp = dfs(xx, y - 1, k);
    ans = (ans + mod - tmp.first) % mod;
    printf("%d\n", ans);
  }
}
