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
import java.io.*;
import java.util.*;

public class cf401e {
  static FastIO in = new FastIO(), out = in;

  static double EPS = 1e-9;
  static int MAX = 100100;
  static long n,m,l,r,p;
  public static void main(String[] args) {
    boolean[] isPrime = new boolean[MAX];
    int[] mu = new int[MAX];
    Arrays.fill(isPrime, true);
    Arrays.fill(mu, 1);
    mu[0] = 0;
    isPrime[0] = isPrime[1] = false;
    for(int i=0; i<MAX; i++)
      if(isPrime[i]) {
        mu[i] = -1;
        for(int j=i+i; j<MAX; j+=i) {
          isPrime[j] = false;
          mu[j] *= -1;
          if(j%(i*1L*i) == 0) mu[j] = 0;
        }
      }
    
    n = in.nextLong();
    m = in.nextLong();
    l = in.nextLong();
    r = in.nextLong();
    p = in.nextLong();
    
    long ans = 0;
    for(long d=1; d<=Math.min(n,m); d++)
      for(long x=1; x<=n/d; x++) {
        long tmp = go(d,x,r*r) - go(d,x,l*l - 1);
        tmp = (tmp*mu[(int) d]*((n-d*x+1)%p))%p;
        ans = (ans + tmp)%p;
      }
    if(l == 1) ans = (ans + 2*n*m + n + m)%p;
    out.println((ans+p)%p);
    out.close();
  }
  static long go(long d, long x, long v) {
    if(v < d*x*d*x) return 0;
    long tmp = Math.min(m/d, (long)Math.floor(Math.sqrt(v - d*x*d*x)+EPS)/d);
    long ret = (2*m - d*(tmp+1) + 2)%p;
    return (ret*tmp)%p;
  }

  static class FastIO extends PrintWriter {
    BufferedReader br;
    StringTokenizer st;

    public FastIO() {
      this(System.in, System.out);
    }

    public FastIO(InputStream in, OutputStream out) {
      super(new BufferedWriter(new OutputStreamWriter(out)));
      br = new BufferedReader(new InputStreamReader(in));
      scanLine();
    }

    public void scanLine() {
      try {
        st = new StringTokenizer(br.readLine().trim());
      } catch (Exception e) {
        throw new RuntimeException(e.getMessage());
      }
    }

    public int numTokens() {
      if (!st.hasMoreTokens()) {
        scanLine();
        return numTokens();
      }
      return st.countTokens();
    }

    public String next() {
      if (!st.hasMoreTokens()) {
        scanLine();
        return next();
      }
      return st.nextToken();
    }

    public double nextDouble() {
      return Double.parseDouble(next());
    }

    public long nextLong() {
      return Long.parseLong(next());
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }
  }
}
