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 double eps = 1e-9;
vector<int> yz[100005];
int n, m, P, L, R, p[100005], prime[100005], miu[100005];
long long ans, l, r;
inline long long calc(int delta_x, int m) {
  long long ret = 0;
  int size = yz[delta_x].size();
  for (int p = 0; p < size; ++p) {
    int d = yz[delta_x][p];
    (ret +=
     miu[d] * (((((1LL * n) << 1) - (m / d + 1) * d + 2) * (m / d) >> 1) % P) +
     P) %= P;
  }
  return ret;
}
int main() {
  scanf("%d%d%d%d%d", &n, &m, &L, &R, &P);
  if (n < m) swap(n, m);
  for (int i = 1; i <= m; ++i)
    for (int j = i; j <= m; j += i) yz[j].push_back(i);
  miu[1] = 1;
  for (int i = 2; i <= m; ++i) {
    if (!p[i])
      miu[prime[++*prime] = p[i] = i] = -1;
    else if (p[i] == p[i / p[i]])
      miu[i] = 0;
    else
      miu[i] = miu[p[i]] * miu[i / p[i]];
    for (int j = 1; j <= *prime && prime[j] <= p[i] && prime[j] * i <= m; ++j)
      p[prime[j] * i] = prime[j];
  }
  int lim = min(m, R);
  for (int delta_x = 1; delta_x <= lim; ++delta_x) {
    r = min((long long)sqrt((1LL * R * R) - (1LL * delta_x * delta_x)),
            1LL * n);
    if (delta_x >= L)
      l = 0;
    else
      l = (long long)(sqrt((1LL * L * L) - (1LL * delta_x * delta_x)) - eps);
    if (l >= r) continue;
    long long tmp = calc(delta_x, r) % P;
    long long tmpp = calc(delta_x, l) % P;
    (ans += ((tmp - tmpp + P) % P) * ((m - delta_x + 1) % P)) %= P;
  }
  (ans <<= 1) %= P;
  if (L <= 1 && 1 <= R)
    (ans += 1LL * n * (m + 1) % P + 1LL * m * (n + 1) % P) %= P;
  printf("%I64d\n", ans);
}
