#include <bits/stdc++.h>
using namespace std;
int cond = 0, multi = 1, gcj = 0;
const int MOD = (int)1e9 + 7;
unordered_map<long long, array<long long, 2> > cache;
array<long long, 2> dp(int r, int c, int k, int len) {
  if (r <= 0 || c <= 0 || k <= 0) return array<long long, 2>();
  k = min(k, len);
  r = min(r, len);
  c = min(c, len);
  long long state = (((((long long)r * MOD) + c) * MOD) + k) * MOD + len;
  auto it = cache.find(state);
  if (it != cache.end()) return it->second;
  if (len == 1) {
    return array<long long, 2>({{1, 1}});
    ;
  }
  r = min(r, len);
  c = min(c, len);
  array<long long, 2> res = array<long long, 2>();
  for (auto dr = (0); dr < (2); ++dr)
    for (auto dc = (0); dc < (2); ++dc) {
      long long nk = (dr == dc) ? k : (k - len / 2);
      array<long long, 2> next =
          dp(r - (len / 2) * dr, c - (len / 2) * dc, nk, len / 2);
      res[1] = (res[1] + next[1]) % MOD;
      res[0] = (res[0] + next[0]) % MOD;
      if (dr != dc) res[0] = (res[0] + next[1] * (long long)(len / 2)) % MOD;
    }
  return cache[state] = res;
}
array<long long, 2> operator+(array<long long, 2> le, array<long long, 2> ri) {
  return array<long long, 2>({{le[0] + ri[0], le[1] + ri[1]}});
}
array<long long, 2> operator-(array<long long, 2> le, array<long long, 2> ri) {
  return array<long long, 2>({{le[0] - ri[0], le[1] - ri[1]}});
}
struct solver {
  void solve() {
    function<int(int)> dfs = [&](int x) { return x; };
    int x1, y1, x2, y2, k;
    cin >> x1 >> y1 >> x2 >> y2 >> k;
    array<long long, 2> res =
        (dp(x2, y2, k, 1 << 30) - dp(x2, y1 - 1, k, 1 << 30) -
         dp(x1 - 1, y2, k, 1 << 30) + dp(x1 - 1, y1 - 1, k, 1 << 30));
    cout << ((res[0] % MOD + MOD) % MOD) << endl;
  }
};
int main(int argc, char** argv) {
  ios::sync_with_stdio(false);
  cond = argc >= 2 && argv[1][0] == 'q' ? 1 << 30 : 0;
  cout.setf(ios::fixed);
  cout.precision(10);
  int t;
  if (multi || gcj)
    cin >> t;
  else
    t = 1;
  for (auto i = (1); i <= (t); ++i) {
    if (cond) cerr << 82 << " " << i << endl;
    if (gcj) cout << "Case #" << i << ": ";
    solver s;
    s.solve();
  }
  return 0;
}
