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;
template <int N>
struct primeTable {
  int sdiv[N], primes[N], pcnt;
  primeTable() {
    pcnt = 0;
    for (int i = 2; i < N; ++i) {
      if (!sdiv[i]) primes[++pcnt] = (sdiv[i] = i);
      for (int j = 1; j <= pcnt && primes[j] * i < N; ++j) {
        sdiv[primes[j] * i] = primes[j];
        if (i % primes[j] == 0) break;
      }
    }
  }
};
primeTable<262144> pT;
inline long long sqr(long long x) { return x * x; }
inline long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }
long long n, m, l, r, p;
int main() {
  cin >> n >> m >> l >> r >> p;
  long long res = 0;
  for (long long dx = 1; dx <= min(r, n); ++dx) {
    long long lo = (long long)ceil(sqrt(max(1LL, sqr(l) - sqr(dx)))),
              hi = min(m, (long long)floor(sqrt(sqr(r) - sqr(dx)))), sum = 0;
    if (lo > hi) {
      continue;
    }
    vector<int> e;
    for (long long p = dx; p > 1; p /= pT.sdiv[p])
      if (e.empty() || e.back() != pT.sdiv[p]) e.push_back(pT.sdiv[p]);
    for (int i = 0; i < (1 << (int)e.size()); ++i) {
      int cur = 1, f = 1;
      for (int j = 0; j < (int)e.size(); ++j)
        if ((i >> j) & 1) cur *= e[j], f = -f;
      long long cnt = hi / cur - (lo - 1) / cur,
                csum = ((m + 1 - ((lo - 1) / cur + 1) * cur) +
                        (m + 1 - hi / cur * cur)) *
                       cnt / 2;
      (sum += f * csum) %= p;
    }
    (res += (n + 1 - dx) * sum) %= p;
  }
  res <<= 1;
  if (l <= 1 && 1 <= r) res += n * (m + 1) + m * (n + 1);
  cout << (res % p + p) % p << endl;
  return 0;
}
