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 n, m, L, R, MOD;
vector<int> divisor[100000 + 10];
long long sum(long long l, long long r, long long p) {
  long long ll = (l - 1) / p, rr = r / p;
  return ((rr - ll) * (m + 1) - p * (ll + 1 + rr) * (rr - ll) / 2) % MOD;
}
int main() {
  cin >> n >> m >> L >> R >> MOD;
  for (int i = 2; i <= 100000; i++)
    if (!divisor[i].size())
      for (int j = i; j <= 100000; j += i) divisor[j].push_back(i);
  long long lo = L, hi = min(m, R);
  long long ans = 0;
  for (long long h = 1; h <= min(n, R); h++) {
    while (lo > 1 && (lo - 1) * (lo - 1) >= L * L - h * h) lo--;
    while (hi * hi > R * R - h * h) hi--;
    if (lo <= hi) {
      long long tmp = 0;
      int sz = divisor[h].size();
      for (int mask = 0; mask < (1 << sz); mask++) {
        int p = 1, cur = 1;
        for (int i = 0; i < sz; i++)
          if (mask & (1 << i)) {
            cur *= -1;
            p *= divisor[h][i];
          }
        tmp = (tmp + cur * sum(lo, hi, p)) % MOD;
      }
      ans = (ans + tmp * (n - h + 1) % MOD) % MOD;
    }
  }
  if (L <= 1 && R >= 1)
    ans = (ans * 2 + n * (m + 1) + m * (n + 1)) % MOD;
  else
    ans = ans * 2 % MOD;
  cout << (ans + MOD) % MOD;
  return 0;
}
