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;
int flag[110000];
int prime[110000][20];
int num[110000];
void Init() {
  int i, j;
  for (i = 2; i <= 100000; i++) {
    if (!flag[i]) {
      for (j = 1; i * j <= 100000; j++) {
        flag[i * j] = 1;
        prime[i * j][num[i * j]++] = i;
      }
    }
  }
}
long long Cal(long long lmin, long long lmax, long long now) {
  lmin = lmin + now - 1;
  lmin /= now;
  lmax /= now;
  return ((n + 1) * (lmax - lmin + 1) -
          now * (lmax * (lmax + 1) - (lmin - 1) * lmin) / 2) %
         mod;
}
int main() {
  Init();
  scanf("%I64d%I64d%I64d%I64d%I64d", &n, &m, &l, &r, &mod);
  long long x, y;
  long long lmin = l, lmax = r;
  long long ans = 0;
  for (y = 1; y <= min(r, m); y++) {
    for (; lmin > 1 && l * l - y * y <= (lmin - 1) * (lmin - 1); lmin--) {
    }
    for (; r * r - y * y < lmax * lmax; lmax--) {
    }
    if (lmin <= lmax && lmin <= n) {
      long long ret = 0;
      for (int i = 0; i < (1 << num[y]); i++) {
        long long p = 1;
        long long temp = 1;
        for (int j = 0; j < num[y]; j++) {
          if ((1 << j) & i) {
            p *= (-1);
            temp *= prime[y][j];
          }
        }
        ret += mod + p * Cal(lmin, min(lmax, n), temp) % mod;
        ret %= mod;
      }
      ans += ret * (m - y + 1);
      ans %= mod;
    }
  }
  if (l == 1)
    ans = (ans * 2 + (n + 1) * m + (m + 1) * n) % mod;
  else
    ans = ans * 2 % mod;
  printf("%I64d\n", ans);
  return 0;
}
