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 = 100000 + 10;
long long n, m;
long long l, r, p;
int d[N][10];
int num[N];
long long ans;
void add(long long &ans, long long v) {
  v = (v % p + p) % p;
  ans = (ans + v) % p;
}
void dfs(long long st, long long v, long long lo, long long ro, long long now,
         long long &c, long long &sm, int fg) {
  for (int i = st + 1; i < num[v]; i++) {
    long long tmp = now * d[v][i];
    long long ll = lo / tmp + (lo % tmp ? 1 : 0);
    long long rr = ro / tmp;
    c += (rr - ll + 1) * fg;
    add(sm, ((rr - ll + 1) * (rr + ll) / 2 % p * tmp % p) * fg);
    dfs(i, v, lo, ro, tmp, c, sm, -1 * fg);
  }
}
void solve(long long v, long long lo, long long ro) {
  if (ro < lo) return;
  long long sm = (long long)(ro - lo + 1) * (ro + lo) / 2 % p;
  long long c = ro - lo + 1;
  dfs(-1, v, lo, ro, 1, c, sm, -1);
  add(ans, (long long)(n - v + 1) * ((long long)(m + 1) % p * c % p - sm));
}
int main() {
  while (cin >> n >> m) {
    cin >> l >> r >> p;
    memset(num, 0, sizeof(num));
    for (int i = 2; i <= n; i++) {
      if (num[i] == 0) {
        for (int j = i; j <= n; j += i) {
          d[j][num[j]++] = i;
        }
      }
    }
    long long lo = l, ro = r;
    ans = 0;
    for (long long i = 1; i <= n; i++) {
      while (l * l - (long long)i * i <= (lo - 1) * (lo - 1) && lo > 1) lo--;
      while (r * r - (long long)i * i < (ro) * (ro) && ro >= 1) ro--;
      solve(i, lo, min(m, ro));
    }
    if (l <= 1)
      cout << (ans * 2 % p + (long long)n * m % p * 2 + n + m) % p << endl;
    else
      cout << ans * 2 % p << endl;
  }
  return 0;
}
