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 N = 100010;
vector<int> v[N];
void prime() {
  for (int i = 2; i < N; i++) {
    if (v[i].size()) continue;
    for (int j = i; j < N; j += i) v[j].push_back(i);
  }
}
long long cal(long long x) { return x * (x + 1) / 2; }
int main() {
  prime();
  long long n, m, L, R, mod;
  cin >> n >> m >> L >> R >> mod;
  long long ans = 0;
  if (L == 1) ans = (n * (m + 1) + m * (n + 1)) % mod;
  for (long long i = 1; i <= n && i <= R; i++) {
    int lt = 1, rt = m, x = -1, y = -1, mid;
    while (lt <= rt) {
      mid = (lt + rt) >> 1;
      if (i * i + (long long)mid * mid > R * R)
        rt = mid - 1;
      else
        y = mid, lt = mid + 1;
    }
    lt = 1, rt = m;
    while (lt <= rt) {
      mid = (lt + rt) >> 1;
      if (i * i + (long long)mid * mid < L * L)
        lt = mid + 1;
      else
        x = mid, rt = mid - 1;
    }
    if (x == -1 || y == -1 || x > y) continue;
    long long sum = 0, tot_len = 0;
    for (int k = 0; k < (1 << v[i].size()); k++) {
      int flag = 1, mul = 1;
      for (int j = 0; j < v[i].size(); j++) {
        if (!(k & (1 << j))) continue;
        flag *= -1;
        mul *= v[i][j];
      }
      sum += flag * (y / mul - (x - 1) / mul);
      tot_len += flag * (mul * cal(y / mul) - mul * cal((x - 1) / mul));
    }
    ans += 2 * (n - i + 1) % mod * ((sum * (m + 1) - tot_len) % mod);
    ans %= mod;
  }
  cout << ans << endl;
  return 0;
}
