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;
template <class T>
inline void smax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void smin(T &a, T b) {
  if (a > b) a = b;
}
long long sum[110000], ans[110000];
long long calc(long long n, long long m, long long r, long long p, int f = 0) {
  long long k, t, tot, res, i, v, g, tmp;
  k = min(n, m);
  tot = 0;
  if (f == 1 && r == 1) return 0;
  for (g = k; g >= 2; g--) {
    ans[g] = 0;
    sum[0] = 0;
    for (i = 1; i <= n / g; i++) {
      sum[i] = sum[i - 1] + (n - i * g + 1);
      sum[i] %= p;
    }
    for (i = 1; i <= m / g; i++) {
      if (i * g >= r) break;
      v = (long long)sqrt(((r) * (r)) - ((i * g) * (i * g))) / g;
      if (!f) {
        while (((g) * (g)) * (((i) * (i)) + ((v) * (v))) <= ((r) * (r))) v++;
        v--;
      } else {
        while (((g) * (g)) * (((i) * (i)) + ((v) * (v))) < ((r) * (r))) v++;
        v--;
      }
      v = min(n / g, v);
      tmp = sum[v];
      ans[g] += tmp * (m - i * g + 1);
      ans[g] %= p;
    }
    for (i = 2; i * g <= k; i++) {
      ans[g] -= ans[g * i];
      ans[g] %= p;
      ans[g] = (ans[g] + p) % p;
    }
    tot += ans[g] % p;
  }
  res = 0;
  for (i = 1; i <= n; i++) {
    if (i >= r) break;
    v = (long long)sqrt(((r) * (r)) - ((i) * (i)));
    if (!f) {
      while (((v) * (v)) + ((i) * (i)) <= ((r) * (r))) v++;
      v--;
    } else {
      while (((v) * (v)) + ((i) * (i)) < ((r) * (r))) v++;
      v--;
    }
    if (v == 0) continue;
    v = min(v, m);
    res += (n - i + 1) * (2 * m - v + 1) * v / 2;
    res %= p;
  }
  res *= 2;
  tot *= 2;
  tot %= p;
  res -= tot;
  res += n * (m + 1) + m * (n + 1);
  res %= p;
  res = (res + p) % p;
  return res;
}
int main() {
  long long n, m, l, r, p, k, t, tot, res, i, u, v, g, tmp;
  scanf("%I64d%I64d%I64d%I64d%I64d", &n, &m, &l, &r, &p);
  res = calc(n, m, r, p) - calc(n, m, l, p, 1);
  res = (res % p + p) % p;
  printf("%I64d\n", res);
  return 0;
}
