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;
template <class T>
inline T sqr(T x) {
  return x * x;
}
const double EPS = 1e-6;
const int INF = 0x3fffffff;
const long long LINF = INF * 1ll * INF;
const double PI = acos(-1.0);
using namespace std;
long long MOD;
vector<int> v[100005];
void init() {
  for (int i = 2; i <= 100000; i++) {
    if (v[i].size() == 0) {
      for (int j = i; j <= 100000; j += i) v[j].push_back(i);
    }
  }
}
long long solve(long long m, long long x, long long y) {
  if (y < 0) return 0;
  long long ans = 0, sum = 0;
  int sz = v[x].size();
  for (int i = 1; i < (1 << sz); i++) {
    long long s = 0, s1 = 0, cnt = 0;
    long long f = 1;
    for (int j = 0; j < sz; j++) {
      if (i & (1 << j)) {
        f *= v[x][j];
        cnt++;
      }
    }
    long long num = y / f;
    s += num;
    s %= MOD;
    s1 += 1ll * (num + 1) * num / 2 % MOD * f % MOD;
    s1 %= MOD;
    if (cnt & 1)
      ans += s, sum += s1;
    else
      ans -= s, sum -= s1;
    ans = (ans % MOD + MOD) % MOD;
    sum = (sum % MOD + MOD) % MOD;
  }
  ans = y - ans;
  ans %= MOD;
  sum = (y + 1) * y / 2 - sum;
  sum %= MOD;
  if (x == 0) {
    if (y > 0)
      ans = m;
    else
      ans = 0;
  } else {
    ans = 2 * (ans * (m + 1) % MOD - sum) % MOD;
    if (x == 1) ans += m + 1;
  }
  ans = (ans % MOD + MOD) % MOD;
  return ans;
}
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
int main(void) {
  long long n, m;
  cin >> n >> m;
  long long l, r;
  cin >> l >> r >> MOD;
  init();
  long long ans = 0;
  for (int i = 0; i <= n; i++) {
    long long low = max(0ll, l * l - 1ll * i * i);
    long long high = min(m * m, r * r - 1ll * i * i);
    low = ceil(sqrt(low));
    high = floor(sqrt(high));
    if (low > high) continue;
    ans += (n - i + 1) % MOD *
           (solve(m, i, high) % MOD - solve(m, i, low - 1) % MOD) % MOD;
    ans = (ans % MOD + MOD) % MOD;
  }
  cout << ans << endl;
  return 0;
}
