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>
int N, M, L, R, P, u[100005], f[100005], p[100005];
long long S(long long n, long long d) {
  return (n * (M + 1) - n * (n + 1) / 2 % P * d) % P;
}
int F(int d, int n) { return S(n / d, d) * u[d] % P; }
void doit() {
  scanf("%d%d%d%d%d", &N, &M, &L, &R, &P), u[1] = 1;
  if (N > M) std::swap(N, M);
  for (int i = 2; i <= N; i++) {
    if (!f[i]) f[i] = i, p[++p[0]] = i, u[i] = -1;
    for (int j = 1; j <= p[0] && i * p[j] <= N && p[j] <= f[i]; j++)
      f[i * p[j]] = p[j], u[i * p[j]] = p[j] < f[i] ? -u[i] : 0;
  }
  int ans = 0;
  if (L == 1) ans += (1ll * N * (M + 1) + 1ll * M * (N + 1)) % P;
  for (int i = 1; i <= N; i++) {
    int l = L <= i ? 1 : ceil(sqrt(1.0 * L * L - 1.0 * i * i)),
        r = std::min(1.0 * M,
                     R <= i ? 0 : floor(sqrt(1.0 * R * R - 1.0 * i * i)));
    long long s = 0;
    if (l > r) continue;
    for (int j = 1; j * j <= i; j++)
      if (i % j == 0) {
        (s += F(j, r) - F(j, l - 1)) %= P;
        if (j * j < i) (s += F(i / j, r) - F(i / j, l - 1)) %= P;
      }
    (ans += s * (N - i + 1) * 2 % P) %= P;
  }
  printf("%d\n", (ans + P) % P);
}
int main() {
  doit();
  return 0;
}
