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;
long long n, m, p, l, r;
long long sum(long long to, long long gap, long long first) {
  if (to == 0) return 0;
  long long tail = first + gap * (to - 1);
  long long ret = (first + tail) * to / 2;
  ret %= p;
  return ret;
}
long long miu[N], cnt[N];
long long solve(long long mr, bool inc) {
  if (mr <= 0) return 0;
  long long ret = 0;
  for (long long i = 1; i <= n; i++) {
    long long temp = n - i + 1;
    int u =
        min(m, (long long)(sqrt(mr * mr - i * i) + ((inc) ? 1e-8 : (-(1e-8)))));
    long long temp1 = sum(u, -1, m);
    for (long long d = 1; d * d <= i && d <= u; d++) {
      if (i % d != 0) continue;
      if (d * d == i) {
        if (d <= u) temp1 += miu[d] * sum(u / d, -d, m - d + 1ll);
      } else {
        if (d <= u) temp1 += miu[d] * sum(u / d, -d, m - d + 1ll);
        long long dd = i / d;
        if (dd <= u) {
          temp1 += miu[dd] * sum(u / dd, -dd, m - dd + 1ll);
        }
      }
    }
    temp1 %= p;
    temp = (temp * temp1) % p;
    if (temp < 0) temp += p;
    ret += temp;
    if (ret >= p) ret -= p;
  }
  ret = ret + ret;
  if (ret >= p) ret -= p;
  if (mr == 1 && inc == false) {
  } else
    ret = (ret + (m + 1ll) * n + m * (n + 1ll)) % p;
  return ret;
}
int main() {
  for (int i = 0; i < N; i++) miu[i] = -2;
  miu[1] = 0;
  for (int i = 2; i < N; i++) {
    if (miu[i] == -2) {
      miu[i] = -1;
      for (int j = 2 * i; j < N; j += i) {
        int tj = j / i;
        if (miu[tj] == 0)
          miu[j] = 0;
        else
          miu[j] = (tj % i == 0) ? 0 : (-miu[tj]);
      }
    }
  }
  cin >> n >> m >> l >> r >> p;
  long long ans = solve(r, true);
  ans -= solve(l, false);
  if (ans < 0) ans += p;
  cout << ans;
}
