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 MaxN = 1000005;
const double eps = 1e-8;
const double DINF = 1e100;
const int INF = 1000000006;
const long long LINF = 1000000000000000005ll;
int pm, mod;
long long f[MaxN], miu[MaxN], prime[MaxN];
bool isprime[MaxN];
void get_miu(int n) {
  memset(isprime, 1, sizeof isprime);
  isprime[1] = 0;
  miu[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (isprime[i]) {
      prime[pm++] = i;
      miu[i] = -1;
    }
    for (int j = 0; j < pm && prime[j] * i <= n; ++j) {
      isprime[prime[j] * i] = 0;
      if (i % prime[j] == 0) {
        miu[i * prime[j]] = 0;
        break;
      } else
        miu[i * prime[j]] = miu[i] * -1;
    }
  }
}
long long sum(long long m, long long n, long long d) {
  return (m * n % mod - (n + 1) * n / 2 % mod * d % mod + mod) % mod;
}
long long Sqrt(long long M) {
  long long L = 0, R = 1000000;
  while (L + 1 < R) {
    long long mid = (L + R) >> 1;
    if (mid * mid <= M)
      L = mid;
    else
      R = mid;
  }
  return L;
}
long long calc(long long n, long long m, long long R) {
  if (!R) return 0;
  memset(f, 0, sizeof f);
  for (long long d = 1; d <= n; ++d) {
    for (long long a = d; a <= n && a <= R; a += d) {
      long long M = min(Sqrt(R - a * a), m);
      f[a] += sum(m + 1, M / d, d) * miu[d] % mod;
      f[a] = (f[a] % mod + mod) % mod;
    }
  }
  long long res = 0;
  for (long long a = 1; a <= n; ++a) {
    res += (long long)(n - a + 1) * f[a] % mod;
    res %= mod;
  }
  return (res * 2 + n * (m + 1) % mod + m * (n + 1) % mod) % mod;
}
int main() {
  int n, m, L, R;
  scanf("%d %d %d %d %d", &n, &m, &L, &R, &mod);
  get_miu(300000);
  cout << (calc(n, m, (long long)R * R) - calc(n, m, (long long)L * L - 1) +
           mod) %
              mod
       << endl;
  return 0;
}
