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>
#pragma comment(linker, "/STACK:36777216")
using namespace std;
int prime[100001], pcnt;
vector<int> vec[100001];
bool is_prime[100001];
void prime_table() {
  memset(is_prime, 1, sizeof(is_prime));
  for (int i = 2; i < 100001; i++) {
    if (is_prime[i]) prime[++pcnt] = i;
    for (int j = 1; j <= pcnt && i * prime[j] < 100001; j++) {
      is_prime[i * prime[j]] = false;
      if (i % prime[j] == 0) break;
    }
  }
  for (int i = 1; i <= pcnt; i++)
    for (int j = prime[i]; j < 100001; j += prime[i])
      vec[j].push_back(prime[i]);
}
int n, m, mod;
long long res = 0;
void dfs(int x, int y, int pos, int num, int k) {
  if (num > y) return;
  if (pos == vec[x].size()) {
    long long t = (y / num);
    long long s1 = t * (m + 1);
    long long s2 = (num + num * t) * t / 2;
    if (k % 2 == 0)
      res += (s1 - s2);
    else
      res -= (s1 - s2);
    res = (res % mod + mod) % mod;
    return;
  }
  dfs(x, y, pos + 1, num * vec[x][pos], k + 1);
  dfs(x, y, pos + 1, num, k);
}
long long calc(int nn, long long x) {
  if (x < 0) return 0;
  int mm = (int)sqrt(x + 0.5);
  if (mm > m) mm = m;
  res = 0;
  dfs(nn, mm, 0, 1, 0);
  res *= 2, res *= (n + 1 - nn), res %= mod;
  return res;
}
int l, r;
long long ANS;
int main() {
  scanf("%d%d", &n, &m);
  scanf("%d%d%d", &l, &r, &mod);
  prime_table();
  for (int i = 1; i <= n; i++) {
    ANS += calc(i, (long long)r * r - (long long)i * i);
    ANS -= calc(i, (long long)l * l - (long long)i * i - 1);
    ANS %= mod;
  }
  if (l <= 1) ANS += (long long)n * (m + 1), ANS += (long long)m * (n + 1);
  ANS = (ANS % mod + mod) % mod;
  printf("%I64d\n", ANS);
}
