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;
const int MAXN = 100000 + 10;
vector<int> t[MAXN];
int n, m, l, r, p, f[MAXN], g[MAXN];
int Getnum(int i, int b) {
  b = min(b, m);
  long long cnt = b / i, Tohka = (long long)cnt * (m + 1) -
                                 (long long)cnt * (1 + cnt) / 2 * i;
  return Tohka % p;
}
int main() {
  cin >> n >> m >> l >> r >> p;
  for (int i = 2; i <= n; ++i)
    if (!t[i].size()) {
      for (int j = i; j <= n; j += i) t[j].push_back(i);
    }
  long long Tohka = 0;
  if (l <= 1)
    Tohka = ((long long)n * (m + 1) % p + (long long)(n + 1) * m % p) % p;
  for (int i = 1; i <= n; ++i) {
    if (i >= r) break;
    int b1 =
        floor(sqrt((double)max((long long)l * l - (long long)i * i - 1, 0ll)));
    int b2 = floor(sqrt((long long)r * r - (long long)i * i));
    if (b1 == b2) continue;
    long long s = 0;
    int cnt = (int)t[i].size();
    for (int j = 0; j < (1 << cnt); ++j) {
      int a = 1, f = 1;
      for (int k = 0; k < cnt; ++k)
        if (j & (1 << k)) a *= t[i][k], f *= -1;
      s = (s + (Getnum(a, b2) - Getnum(a, b1)) * f + p) % p;
    }
    s *= 2;
    Tohka = ((long long)Tohka + (long long)s * (n + 1 - i) % p) % p;
  }
  cout << Tohka << endl;
  fclose(stdin);
  fclose(stdout);
  return 0;
}
