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;
inline long long read() {
  long long x = 0, f = 1, ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') {
      f = -1;
    }
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
long long n, m, l, r;
long long mod;
vector<long long> p;
long long sum;
inline long long dfs(long long d, long long x, long long y) {
  if (d == p.size()) {
    long long n = abs(y / x);
    sum = (sum + 1ll * n * (n + 1) / 2 % mod * x % mod) % mod;
    return y / x;
  }
  return (dfs(d + 1, x, y) + dfs(d + 1, -x * p[d], y));
}
inline long long gcdnumber(long long a, long long y) {
  p.clear();
  for (long long i = 2; i * i <= a; i++) {
    if (a % i == 0) {
      p.push_back(i);
      while (a % i == 0) a /= i;
    }
  }
  sum = 0;
  if (a != 1) p.push_back(a);
  return dfs(0, 1, y);
}
inline long long calc(long long radiu, long long add) {
  long long y = radiu;
  long long res = 0;
  for (long long i = 1; i <= radiu; i++) {
    while (y && (long long)(i * i + y * y) > 1ll * radiu * radiu - add) y--;
    if (y >= m) y = m;
    if (i <= n && y > 0) {
      long long tmp = gcdnumber(i, y);
      res = (res + 1ll * (n - i + 1) * (1ll * tmp * (m + 1) % mod - sum + mod) %
                       mod) %
            mod;
    }
  }
  return res;
}
int main() {
  n = read(), m = read();
  l = read(), r = read(), mod = read();
  long long ans = 0;
  if (l == 1) ans = (1ll * n * (m + 1) % mod + 1ll * m * (n + 1) % mod) % mod;
  ans = (ans + (calc(r, 0) - calc(l, 1) + mod) % mod * 2 % mod) % mod;
  cout << ans << endl;
  return 0;
}
