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 int N = 150000;
int primeDivisor[N + 1], m, n, mod;
void eratos() {
  for (int i = 2; i * i <= N; ++i)
    if (primeDivisor[i] == 0)
      for (int j = i * i; j <= N; j += i)
        if (primeDivisor[j] == 0) primeDivisor[j] = i;
  for (int i = 2; i <= N; ++i)
    if (primeDivisor[i] == 0) primeDivisor[i] = i;
}
vector<int> getFactor(int x) {
  vector<int> res;
  for (; x > 1; x /= primeDivisor[x])
    if (res.empty() || res.back() != primeDivisor[x])
      res.push_back(primeDivisor[x]);
  return res;
}
int count(long long lim) {
  int res = 0;
  for (long long y = 1, x = min(n, (int)sqrt(lim) + 5); y <= m && y * y <= lim;
       ++y) {
    while (x > 0 && y * y + x * x > lim) --x;
    if (x <= 0) break;
    vector<int> factor = getFactor(y);
    int s = factor.size();
    for (int mask = 0; mask < 1 << s; ++mask) {
      int v = 1, mul = 1;
      for (int i = 0; i < s; ++i)
        if ((mask & 1 << i) != 0) v *= factor[i], mul *= -1;
      long long w = x / v;
      res = (res +
             mul * (w * (n + 1) - w * (w + 1) * v / 2) % mod * (m - y + 1)) %
            mod;
    }
  }
  return 2 * res % mod;
}
int main() {
  ios::sync_with_stdio(false);
  for (int l, r; cin >> m >> n >> l >> r >> mod;) {
    eratos();
    int res = (count(1LL * r * r) - count(1LL * l * l - 1)) % mod;
    if (l == 1) res = (res + 2LL * m * n + m + n) % mod;
    cout << (res + mod) % mod << '\n';
  }
  return 0;
}
