#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
pair<long long, long long> s(int x, int y, long long k) {
  if (y > x) return s(y, x, k);
  if (y == 0) return make_pair(0ll, 0ll);
  if (k <= 0) return make_pair(0ll, 0ll);
  long long t;
  for (t = 30; t >= 0; t--)
    if ((1 << t) <= x) break;
  t = (1 << t);
  if (y <= t) {
    pair<long long, long long> pr = s(x - t, y, k - t);
    pr.second += pr.first * t;
    pr.second %= mod;
    pr.first += min(t, k) * (long long)y;
    pr.first %= mod;
    pr.second += (((min(t, k) + 1ll) * min(t, k) / 2ll) % mod) * (long long)y;
    pr.second %= mod;
    return pr;
  } else {
    pair<long long, long long> pr1 = s(x - t, t, k - t),
                               pr2 = s(y - t, t, k - t),
                               pr = s(x - t, y - t, k);
    pr1.second += pr1.first * t;
    pr1.second %= mod;
    pr2.second += pr2.first * t;
    pr2.second %= mod;
    pr.first += min(t, k) * t;
    pr.first %= mod;
    pr.second += (((min(t, k) + 1ll) * min(t, k) / 2ll) % mod) * t;
    pr.second %= mod;
    pr.first += pr1.first + pr2.first;
    pr.second += pr1.second + pr2.second;
    pr.first %= mod;
    pr.second %= mod;
    return pr;
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) {
    int a, b, c, d;
    long long k;
    cin >> a >> b >> c >> d >> k;
    a--, b--;
    long long ans = s(c, d, k).second - s(a, d, k).second - s(b, c, k).second +
                    s(a, b, k).second;
    ans %= mod;
    ans += mod;
    ans %= mod;
    cout << ans << endl;
  }
}
