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;
const int maxn = 100050, maxp = 1000, maxps = 200;
int pr[maxps], whe[maxn] = {0}, ps = 0;
long long n, m, L, R, p, ans = 0;
int fa[maxps], fs = 0;
int Sqrt(long long x) {
  if (x < 0)
    return 0;
  else if (x > m * m)
    return m;
  return sqrt(x);
}
void init() {
  int i, j;
  for (i = 2; i < maxp; i++) {
    if (!whe[i]) pr[ps++] = i;
    for (j = 0; j < ps && i * pr[j] < maxn; j++) {
      whe[i * pr[j]] = 1;
      if (!(i % pr[j])) break;
    }
  }
}
int dfs(int k, bool u, int cur, int now) {
  int i;
  long long s = 0;
  if (cur == fs) {
    long long t = k / now;
    s = (t * (m + 1) - t * (t + 1) / 2 * now);
    return (-2 * u + 1) * s % p;
  }
  s = dfs(k, u, cur + 1, now);
  s += dfs(k, !u, cur + 1, now * fa[cur]);
  return s % p;
}
int calc(int x, int k) {
  int i, x0 = x;
  if (!k) return 0;
  fs = 0;
  memset(fa, 0, sizeof(fa));
  for (i = 0; i < ps; i++)
    if (!(x0 % pr[i])) {
      while (!(x0 % pr[i])) x0 /= pr[i];
      fa[fs++] = pr[i];
    }
  if (x0 > 1) fa[fs++] = x0;
  return dfs(k, 0, 0, 1);
}
int main() {
  long long x;
  init();
  scanf("%I64d%I64d%I64d%I64d%I64d", &n, &m, &L, &R, &p);
  for (x = 1; x <= min(n, R - 1); x++) {
    int l = Sqrt(L * L - x * x - 1), r = Sqrt(R * R - x * x);
    ans += (n - x + 1) * (calc(x, r) - calc(x, l)) % p;
    ans %= p;
  }
  ans *= 2;
  if (L == 1) ans += n * (m + 1) + m * (n + 1);
  ans %= p;
  if (ans < 0) ans += p;
  printf("%I64d\n", ans);
  return 0;
}
