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, p, x, y;
int minprime[160005], pz[30], nz;
void init() {
  for (int i = 2; i < 160000; i++) {
    minprime[i] = i;
  }
  for (int i = 2; i < 400; i++) {
    for (int j = i * i; j < 160000; j += i) {
      if (minprime[j] == j) minprime[j] = i;
    }
  }
}
bool getxy(long long z, long long &x, long long &y) {
  if (z >= r) return false;
  while (x && x * x + z * z >= l * l) x--;
  while (y && y * y + z * z > r * r) y--;
  return true;
}
void buildz(int z) {
  nz = 0;
  while (z > 1) {
    pz[nz] = minprime[z];
    while (minprime[z] == pz[nz]) {
      z /= minprime[z];
    }
    nz++;
  }
}
long long calsum(long long mx) {
  long long ans = 0;
  for (int i = 0; i < (1 << nz); i++) {
    long long cur = 1;
    long long sgn = 1;
    for (int j = 0; j < nz; j++) {
      if ((1 << j) & i) {
        sgn *= -1;
        cur *= pz[j];
      }
    }
    long long num = mx / cur;
    long long head = m + 1 - cur;
    long long tail = m + 1 - cur * num;
    ans += (sgn * (head + tail) * num) % p;
    ans %= p;
  }
  return ans;
}
int main() {
  init();
  while (cin >> n >> m) {
    long long ans = 0;
    cin >> l >> r >> p;
    x = m;
    y = m;
    for (long long i = 1; i <= n; i++) {
      if (getxy(i, x, y)) {
        long long mtr = n - i + 1;
        buildz(i);
        long long mtc = (calsum(y) - calsum(x)) % p;
        ans += mtr * mtc % p;
        ans %= p;
        ans = (ans + p) % p;
      }
    }
    if (l <= 1 && 1 <= r) {
      ans += n * (m + 1) + m * (n + 1);
      ans %= p;
    }
    cout << ans << endl;
  }
  return 0;
}
