This problem was deleted from the contest, because it was used previously at another competition.

Input

Output

Examples

Input

1 1
1 2 100


Output

6
#include <bits/stdc++.h>
using namespace std;
int c[110000];
long long n, m, l, r;
long long ans, p;
vector<int> g;
long long solve(long long z, long long le, long long ri) {
  int l = 0;
  while (z > 1) {
    if ((l == 0) || (g[l - 1] != c[z])) {
      g.push_back(c[z]);
      ++l;
    }
    z /= c[z];
  }
  long long ret = 0, cc, tmp, u, d;
  for (int i = 0; i < (1 << l); i++) {
    cc = 1;
    tmp = 1;
    for (int j = 0; j < l; j++) {
      if ((1 << j) & i) {
        cc = -cc;
        tmp *= g[j];
      }
    }
    u = ri / tmp;
    d = max((le - 1) / tmp, 0ll);
    ret = ret + cc * (u - d) * (2 * m + 2 - (u + d + 1) * tmp) / 2;
    ret = (ret % p + p) % p;
  }
  return ret;
}
int main() {
  c[1] = 1;
  for (int i = 2; i <= 100000; i++) {
    if (c[i] != 0) continue;
    c[i] = i;
    if (i > 400) continue;
    for (int j = i * i; j <= 100000; j += i) {
      if (c[j] == 0) c[j] = i;
    }
  }
  cin >> n >> m >> l >> r >> p;
  ans = 0;
  long long tle, ri, le;
  if (l == 1) {
    ans = ((n + 1) * m) % p;
    ans += (n * (m + 1)) % p;
    ans %= p;
  }
  for (long long dx = 1; dx <= min(r, n); dx++) {
    tle = max(0ll, l * l - dx * dx);
    le = sqrt(tle);
    if (le * le != tle) ++le;
    le = max(1ll, le);
    ri = r * r - dx * dx;
    ri = sqrt(ri);
    ri = min(ri, m);
    if (le > ri) continue;
    g.clear();
    ans += (n - dx + 1) * 2 * solve(dx, le, ri);
    ans %= p;
  }
  cout << ans << endl;
  return 0;
}
