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 long long inf = 1e18 + 7;
const long long mod = 1e9 + 7;
const double eps = 1e-9;
const double PI = 2 * acos(0.0);
const double E = 2.71828;
long long n, m;
long long l, r, p;
vector<int> a[1000005];
long long res = 0;
long long go(long long l, long long r, long long val) {
  long long res = 0;
  long long L = (l + val - 1) / val;
  long long R = r / val;
  res += (R - L + 1) * (m - R * val + 1);
  long long cnt = R - L;
  res += val * cnt * (cnt + 1) / 2;
  return res % p;
}
int main(void) {
  cin >> n >> m;
  cin >> l >> r >> p;
  for (int i = 2; i <= n; ++i) {
    if (a[i].empty()) {
      for (int j = i; j <= n; j += i) {
        a[j].push_back(i);
      }
    }
  }
  long long L = l, R = r;
  for (long long i = 1; i <= min(r, n); ++i) {
    while (L > 1 && (L - 1) * (L - 1) + i * i >= l * l) {
      --L;
    }
    while (R >= L && R * R + i * i > r * r) {
      --R;
    }
    R = min(R, m);
    if (L > R) {
      continue;
    }
    int sz = a[i].size();
    long long cnt = 0;
    for (long long(j) = 0; (j) < (long long)(1 << sz); (j)++) {
      long long mul = 1, val = 1;
      for (long long(x) = 0; (x) < (long long)(sz); (x)++) {
        if (~j & (1 << x)) {
          continue;
        }
        mul *= -1;
        val *= a[i][x];
      }
      cnt += mul * go(L, R, val);
    }
    res = (res + cnt * (n - i + 1) % p + p) % p;
  }
  res = (res + res) % p;
  if (l == 1) {
    res = (res + (n + 1) * m + (m + 1) * n) % p;
  }
  printf("%I64d\n", res);
  return 0;
}
