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 int n, m, l, r, mod, res, num, sum[100005], nco_prime;
vector<long long int> g[100005];
bool used[100005];
void sieve() {
  long long int i, j;
  for (i = 2; i <= 100000; i += 2) g[i].push_back(2);
  for (i = 3; i <= 100001; i += 2) {
    if (used[i] == false) {
      for (j = i; j <= 100001; j += i) {
        used[j] = true;
        g[j].push_back(i);
      }
    }
  }
}
void backtrack(long long int i, long long int x, long long int y,
               long long int mul, long long int timer) {
  long long int sss;
  if (i == g[x].size()) {
    if (timer == 0) return;
    if (timer % 2) {
      sss = y / mul;
      sss *= mul;
      nco_prime = (nco_prime + mod -
                   (((sss - mul) / mul + 1) * (sss + mul) / 2) % mod) %
                  mod;
      sss = y / mul;
      nco_prime = (nco_prime + (sss * (m + 1)) % mod) % mod;
    } else {
      sss = y / mul;
      sss *= mul;
      nco_prime = (nco_prime + ((sss - mul) / mul + 1) * (sss + mul) / 2) % mod;
      sss = y / mul;
      nco_prime = (nco_prime + mod - (sss * (m + 1)) % mod) % mod;
    }
    return;
  }
  backtrack(i + 1, x, y, mul, timer);
  sss = y / g[x][i];
  sss *= g[x][i];
  backtrack(i + 1, x, y, mul * g[x][i], timer + 1);
}
int main() {
  long long int i, j, x, y, m1, m2, ss, s1, s2;
  sieve();
  cin >> n >> m >> l >> r >> mod;
  for (i = 1; i <= m; i++) sum[i] = sum[i - 1] + (m - i + 1);
  if (l == 1) res = (m * (n + 1) + n * (m + 1)) % mod;
  for (x = 1; x <= min(r - 1, n); x++) {
    num = x;
    ss = r * r - x * x;
    m2 = (long long int)sqrt((long double)ss);
    m2 = min(m2, m);
    ss = l * l - x * x;
    if (x < l) {
      m1 = (long long int)sqrt((long double)ss);
      if (m1 * m1 + x * x < l * l) m1++;
    } else
      m1 = 1;
    if (m1 > m2) continue;
    ss = sum[m2] - sum[m1 - 1];
    nco_prime = 0LL;
    backtrack(0, x, m1 - 1, 1, 0);
    s1 = nco_prime;
    nco_prime = 0LL;
    backtrack(0, x, m2, 1, 0);
    s2 = nco_prime;
    res = (res + ((ss - (s2 - s1)) % mod) * (n - x + 1) * 2LL) % mod;
  }
  cout << res << endl;
  return 0;
}
