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;
int p;
int n, m;
int search(long long int x) {
  int s = 0, e = 200000;
  while (e - s > 1) {
    int med = (s + e) / 2;
    if ((long long int)med * (long long int)med > x)
      e = med;
    else
      s = med;
  }
  return s;
}
long long int cnt(long long int dist) {
  if (dist < 1) return 0;
  long long int ret = (long long int)n * (long long int)(m + 1) +
                      (long long int)m * (long long int)(n + 1);
  ret %= p;
  for (int i = 1; i <= n; i++) {
    if (dist < (long long int)i * (long long int)i) break;
    int zan = search(dist - (long long int)i * (long long int)i);
    zan = min(zan, m);
    if (zan == 0) break;
    int lim = i;
    long long int sum = 0;
    vector<int> pr;
    for (int j = 2; j * j <= lim; j++) {
      if (lim % j == 0) {
        pr.push_back(j);
        while (lim % j == 0) lim /= j;
      }
    }
    if (lim != 1) pr.push_back(lim);
    for (int S = 0; S < 1 << pr.size(); S++) {
      int cnt = 0, pd = 1;
      for (int j = 0; j < pr.size(); j++) {
        if (S >> j & 1) {
          cnt++;
          pd *= pr[j];
        }
      }
      int all = zan / pd;
      long long int val =
          (long long int)(m + 1) * (long long int)all -
          (long long int)pd * (long long int)all * (long long int)(all + 1) / 2;
      val %= p;
      if (cnt % 2 == 0)
        sum += val;
      else
        sum -= val;
      if (sum < 0) sum += p;
      sum %= p;
    }
    ret = (ret + (long long int)(n - i + 1) * sum * 2LL % p) % p;
  }
  return ret;
}
int main() {
  int l, r;
  scanf("%d %d", &n, &m);
  scanf("%d %d %d", &l, &r, &p);
  long long int ret = cnt((long long int)r * (long long int)r) -
                      cnt((long long int)(l - 1) * (long long int)(l + 1));
  if (ret < 0) ret += p;
  printf("%llld\n", ret);
  return 0;
}
