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;
long long l, r, m, n, res = 0, mod;
int fac[1000001];
long long f(long long x, long long y) {
  long long tmp = (2 * m + 1 - y) * y;
  vector<int> v;
  while (x > 1) {
    if (v.empty() || v[v.size() - 1] != fac[x]) v.push_back(fac[x]);
    x /= fac[x];
  }
  int t = v.size();
  for (long long i = 1; i < (1 << t); i++) {
    long long cnt = 0, prod = 1;
    for (int j = 0; j < t; j++)
      if (1 & i >> j) prod *= v[j], cnt++;
    if (cnt & 1)
      tmp = (tmp - ((y / prod) * (2 * m + 2 - (y - y % prod) - prod)) % mod +
             mod) %
            mod;
    else
      tmp = (tmp + ((y / prod) * (2 * m + 2 - (y - y % prod) - prod)) % mod +
             mod) %
            mod;
  }
  return tmp;
}
int main() {
  for (int i = 1000000; i >= 2; i--)
    for (int j = i; j < 1000001; j += i) fac[j] = i;
  cin >> n >> m >> l >> r >> mod;
  for (long long i = 1; i <= min(r, n); i++) {
    long long a = i < l ? ceil(sqrt(l * l - i * i)) : 0;
    long long b = floor(sqrt(r * r - i * i));
    if (a > m) continue;
    a = max(1LL, a);
    b = min(m, b);
    if (b < a) continue;
    res += ((n + 1 - i) * f(i, b)) % mod;
    res %= mod;
    res += mod - ((n + 1 - i) * f(i, a - 1)) % mod;
    res %= mod;
  }
  if (l == 1) res = (res + (n + m) + (2 * n * m) % mod) % mod;
  cout << res << endl;
  return 0;
}
