#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
void add(long long &x, long long y) {
  x += y;
  x %= MOD;
}
void sub(long long &x, long long y) {
  x = x - y + (long long)MOD;
  x %= MOD;
}
long long calc(long long x, long long y, long long k, long long d = 0) {
  if (x > y) {
    swap(x, y);
  }
  if (x <= 0 || k <= 0) {
    return 0;
  }
  long long p = (1ll << ((int)log2(y)));
  long long ans = 0;
  long long t = min(p, k);
  long long rowSum = ((1 + t) * t / 2) % MOD;
  if (x <= p) {
    ans = (rowSum * (x % MOD)) % MOD;
    long long rem = (((t * x) % MOD) * (d % MOD)) % MOD;
    add(ans, (rem + calc(x, y - p, k - p, d + p)) % MOD);
    return ans;
  }
  ans = ((rowSum * p) % MOD + (((p * t) % MOD) * (d % MOD)) % MOD) % MOD;
  add(ans, calc(x - p, y - p, k, d));
  add(ans, calc(x - p, p, k - p, d + p));
  add(ans, calc(p, y - p, k - p, d + p));
  return ans;
}
int main(void) {
  long long x1, y1, x2, y2, k, ans;
  int q;
  scanf("%d", &q);
  while (q--) {
    scanf("%lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &k);
    ans = 0;
    add(ans, calc(x2, y2, k));
    sub(ans, calc(x2, y1 - 1, k));
    sub(ans, calc(x1 - 1, y2, k));
    add(ans, calc(x1 - 1, y1 - 1, k));
    printf("%lld\n", ans);
  }
  return 0;
}
