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;
int i, j, k, n, m, mo;
long long an, s, sum, l, r, L, R;
int f[100010], p[100010], g[100010], F[100010];
void dfs(int x, int y, int z) {
  if (x > *g) {
    int fi = L / y, en = R / y;
    if (fi == en) return;
    long long l = (fi + 1) * y, r = en * y;
    long long re = (R + 1) * (en - fi) - (l + r) * (en - fi) / 2;
    re %= mo;
    sum = (sum + re * z) % mo;
    s += (en - fi) * z;
    return;
  }
  dfs(x + 1, y, z);
  dfs(x + 1, y * g[x], z * -1);
}
inline long long work(int len) {
  int k = len;
  long long re = 0;
  s = sum = *g = 0;
  for (; k > 1; k /= p[f[k]])
    if (g[*g] != p[f[k]]) g[++*g] = p[f[k]];
  dfs(1, 1, 1);
  re = s * (m - 1 - R) + sum;
  re %= mo;
  return re * 2 % mo;
}
int main() {
  for (i = 2; i <= 100010 - 1; i++) {
    if (!f[i]) p[++*p] = i, f[i] = *p;
    for (j = 1; j <= f[i] && i * p[j] < 100010; j++) f[i * p[j]] = j;
  }
  scanf("%d%d%I64d%I64d%d", &n, &m, &l, &r, &mo);
  n++, m++;
  if (l == 1) an = ((long long)n * (m - 1) + (long long)(n - 1) * m) % mo;
  L = m - 1, R = m - 1;
  for (i = 1; i <= n - 1; i++) {
    for (; L && L * L + 1ll * i * i >= l * l; L--)
      ;
    for (; R && R * R + 1ll * i * i > r * r; R--)
      ;
    if (L >= R) continue;
    an = (an + work(i) * (n - i)) % mo;
  }
  if (an < 0) an += mo;
  printf("%I64d\n", an);
  return 0;
}
