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 mo, n, m, l, r;
int prime[10];
pair<int, int> count(int x, int ql) {
  int ptot = 0;
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) prime[++ptot] = i;
    while (x % i == 0) x /= i;
  }
  if (x > 1) prime[++ptot] = x;
  int cnt = 0, sum = 0, fl;
  for (int i = 1; i < (1 << ptot); i++) {
    int cur = 1, cc = 0;
    for (int j = 1; j <= ptot; j++)
      if ((i >> (j - 1)) & 1) cur *= prime[j], cc++;
    if (cc & 1)
      fl = 1;
    else
      fl = -1;
    cnt = (cnt + 1ll * fl * (ql / cur)) % mo;
    sum = (sum +
           (1ll * fl * (cur + cur + (ql / cur - 1) * cur) * (ql / cur) / 2) %
               mo) %
          mo;
  }
  return make_pair(cnt, sum);
}
pair<int, int> countprime(int x, int ql, int qr) {
  pair<int, int> L = count(x, ql - 1), R = count(x, qr);
  int cnt = (((qr - ql + 1) - (R.first - L.first)) % mo + mo) % mo;
  int sum = (((1ll * (ql + qr) * (qr - ql + 1) / 2) % mo -
              (R.second - L.second) % mo) %
                 mo +
             mo) %
            mo;
  return make_pair(cnt, sum);
}
int main() {
  cin >> n >> m >> l >> r >> mo;
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    int ql = max(1, (int)ceil(sqrt(1.0 * l * l - 1.0 * i * i)));
    int qr = min(m, (int)floor(sqrt(1.0 * r * r - 1.0 * i * i)));
    if (ql <= qr) {
      pair<int, int> t = countprime(i, ql, qr);
      ans = (ans + 1ll * (n - i + 1) % mo *
                       (1ll * t.first * (m + 1) % mo - t.second) % mo) %
            mo;
    }
  }
  ans = 2ll * ans % mo;
  if (l == 1)
    ans = (ans + 1ll * n * (m + 1) % mo + 1ll * m * (n + 1) % mo) % mo;
  cout << (ans + mo) % mo << endl;
  return 0;
}
