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>
long long n, m, l, r, p;
long long min(long long x, long long y) {
  if (x < y) return x;
  return y;
}
long long ask(long long L, long long R, long long x) {
  long long Lx = L / x, Rx = R / x;
  if (L % x) Lx++;
  if (Lx > Rx) return 0;
  long long xn = m - Lx * x + 1, x1 = m - Rx * x + 1;
  long long xs = (xn - x1) / x + 1;
  return (((x1 + xn) * xs) / 2) % p;
}
int maxn = 100000;
int f[100050];
long long ss[100050], size;
long long sta[20], top;
long long Ans;
int xx[20];
long long LL, RR;
void go(int v, long long Lcm, int _) {
  if (v == top + 1) {
    if (_)
      Ans += ask(LL, RR, Lcm);
    else
      Ans -= ask(LL, RR, Lcm);
    Ans %= p;
    return;
  }
  xx[v] = 1;
  go(v + 1, Lcm * sta[v], _ ^ 1);
  xx[v] = 0;
  go(v + 1, Lcm, _);
}
long long get(long long L, long long R, long long x) {
  top = 0;
  long long xx = x;
  for (int i = 1; ss[i] * ss[i] <= x; i++)
    if (x % ss[i] == 0) {
      sta[++top] = ss[i];
      for (; x % ss[i] == 0; x /= ss[i])
        ;
    }
  if (x > 1) sta[++top] = x;
  Ans = 0;
  LL = L, RR = R;
  x = xx;
  go(1, 1, 1);
  Ans *= (n - x + 1);
  Ans %= p;
  return Ans;
}
int main() {
  scanf("%I64d%I64d%I64d%I64d%I64d", &n, &m, &l, &r, &p);
  for (int i = 2; i <= maxn; i++)
    if (!f[i]) {
      ss[++size] = i;
      for (int j = 2; i * j <= maxn; j++) f[i * j] = 1;
    }
  long long N = min(r - 1, n);
  long long ans = 0;
  for (long long x = 1; x <= N; x++) {
    long long L = (long long)ceil(sqrt(l * l - x * x)),
              R = (long long)floor(sqrt(r * r - x * x));
    if (l * l - x * x <= 0) L = 1;
    if (R > m) R = m;
    ans += get(L, R, x);
    ans %= p;
  }
  ans = (ans + ans) % p;
  if (l <= 1 && 1 <= r) ans += n * (m + 1) + m * (n + 1);
  ans %= p;
  if (ans < 0) ans += p;
  printf("%I64d\n", ans);
}
