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 MAXN = 1e5 + 5;
long long prime[MAXN];
void sieve() {
  for (int p = 2; p < MAXN; p++) {
    if (prime[p]) continue;
    for (int j = p; j < MAXN; j += p) prime[j] = p;
  }
}
long long n, m, L, R, mod = 10000;
vector<long long> prod(vector<long long> &a, vector<long long> &b) {
  vector<long long> res;
  for (auto x : a)
    for (auto y : b) res.push_back((x * y) % mod);
  return res;
}
vector<long long> mdivs(long long x) {
  if (x == 1) return {1};
  long long p = prime[x];
  while (x % p == 0) x /= p;
  vector<long long> od = mdivs(x), pr = {1, -p};
  return prod(pr, od);
}
long long solve(long long upper) {
  if (upper == 0) return 0;
  long long ans = n * (m + 1) + m * (n + 1);
  if (upper == 1) return ans;
  for (long long x = 1; x <= n; x++) {
    if (x * x >= upper) break;
    long long B = sqrt(upper - x * x);
    while (B * B + x * x > upper) B--;
    while ((B + 1) * (B + 1) + x * x <= upper) B++;
    B = min(B, m);
    for (auto d : mdivs(x)) {
      long long mul = 1;
      if (d < 0) {
        d = -d;
        mul = -1;
      }
      long long c = B / d;
      long long add = (c * (m + 1) - d * ((c * (c + 1)) / 2)) % mod;
      add = add * 2 * mul * (n - x + 1);
      ans = (ans + add) % mod;
    }
  }
  return ans;
}
int main() {
  sieve();
  cin >> n >> m >> L >> R >> mod;
  long long res = solve(R * R) - solve(L * L - 1);
  res %= mod;
  if (res < 0) res += mod;
  cout << res << '\n';
}
