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;
long long ans;
int d[100005][10], num[100005];
inline long long pif(long long x, long long y) {
  if (x % y)
    return x / y + 1;
  else
    return x / y;
}
inline long long calc(long long x, long long L, long long R) {
  long long Fir = n - 1ll * pif(L, x) * x + 1;
  long long End = n - 1ll * R / x * x + 1;
  long long num = (Fir - End) / x + 1;
  return (Fir + End) * num / 2ll;
}
int main() {
  scanf("%I64d%I64d", &n, &m);
  scanf("%I64d%I64d%I64d", &l, &r, &mod);
  for (int i = 2; i <= m; i++) {
    if (num[i]) continue;
    for (int j = i; j <= m; j += i) d[j][++num[j]] = i;
  }
  if (l <= 1) {
    ans += 1ll * n * (m + 1) % mod;
    ans += 1ll * m * (n + 1) % mod;
  }
  for (int i = 1, lo = n, hi = n; i <= m; i++) {
    while ((1ll * (lo - 1) * (lo - 1) + 1ll * i * i >= 1ll * l * l) && lo) lo--;
    while ((1ll * hi * hi + 1ll * i * i > 1ll * r * r) && hi) hi--;
    if (!lo) lo++;
    if (lo <= hi && 1ll * lo * lo + 1ll * i * i >= 1ll * l * l &&
        1ll * hi * hi + 1ll * i * i <= 1ll * r * r) {
      int tmp = (1 << num[i]);
      long long query = 0;
      for (int x = 0; x < tmp; x++) {
        long long px = 1, py = 1;
        for (int j = 1, k = x; j <= num[i]; j++, k >>= 1)
          if (k & 1) {
            px *= d[i][j];
            py = -py;
          }
        query = (query + py * calc(px, lo, hi) % mod) % mod;
      }
      ans = (ans + 2ll * (m - i + 1) * query % mod) % mod;
      if (ans < 0) ans += mod;
    }
  }
  printf("%I64d\n", ans);
  return 0;
}
