Lakhesh loves to make movies, so Nephren helps her run a cinema. We may call it No. 68 Cinema.

<image>

However, one day, the No. 68 Cinema runs out of changes (they don't have 50-yuan notes currently), but Nephren still wants to start their business. (Assume that yuan is a kind of currency in Regulu Ere.)

There are three types of customers: some of them bring exactly a 50-yuan note; some of them bring a 100-yuan note and Nephren needs to give a 50-yuan note back to him/her; some of them bring VIP cards so that they don't need to pay for the ticket.

Now n customers are waiting outside in queue. Nephren wants to know how many possible queues are there that they are able to run smoothly (i.e. every customer can receive his/her change), and that the number of 50-yuan notes they have after selling tickets to all these customers is between l and r, inclusive. Two queues are considered different if there exists a customer whose type is different in two queues. As the number can be large, please output the answer modulo p.

Input

One line containing four integers n (1 ≤ n ≤ 105), p (1 ≤ p ≤ 2·109), l and r (0 ≤ l ≤ r ≤ n). 

Output

One line indicating the answer modulo p.

Examples

Input

4 97 2 3


Output

13


Input

4 100 0 4


Output

35

Note

We use A, B and C to indicate customers with 50-yuan notes, customers with 100-yuan notes and customers with VIP cards respectively.

For the first sample, the different possible queues that there are 2 50-yuan notes left are AAAB, AABA, ABAA, AACC, ACAC, ACCA, CAAC, CACA and CCAA, and the different possible queues that there are 3 50-yuan notes left are AAAC, AACA, ACAA and CAAA. So there are 13 different queues satisfying the first sample. Similarly, there are 35 different queues satisfying the second sample.
#include <bits/stdc++.h>
using namespace std;
const long long N = 100001;
long long n, p, phi, l, r;
long long ans;
long long g[N][30], f[N], F[N], pr[30], t[30];
long long mi(long long a, long long b) {
  long long s = 1;
  for (; b; b >>= 1, a = (long long)a * a % p)
    if (b & 1) s = (long long)s * a % p;
  return s;
}
long long c(long long a, long long b) {
  if (a < b) return 0;
  long long s = (long long)f[a] * F[b] % p * F[a - b] % p;
  for (long long i = 1; i <= pr[0]; ++i) t[i] = g[a][i] - g[b][i] - g[a - b][i];
  for (long long i = 1; i <= pr[0]; ++i) s = (long long)s * mi(pr[i], t[i]) % p;
  return s;
}
void init() {
  f[0] = F[0] = 1;
  long long P = p, top = (long long)sqrt(p + 1);
  phi = p;
  for (long long i = 2; i <= top; ++i)
    if (P % i == 0) {
      pr[++pr[0]] = i;
      phi = phi / i * (i - 1);
      while (P % i == 0) P /= i;
    }
  if (P > 1) pr[++pr[0]] = P, phi = phi / P * (P - 1);
  for (long long i = 1; i <= n; ++i) {
    long long num = i;
    for (long long j = 1; j <= pr[0]; ++j)
      while (num % pr[j] == 0) num /= pr[j], g[i][j]++;
    for (long long j = 1; j <= pr[0]; ++j) g[i][j] += g[i - 1][j];
    f[i] = f[i - 1] * num % p;
    F[i] = mi(f[i], phi - 1);
  }
}
int main() {
  cin >> n >> p >> l >> r;
  init();
  for (long long len = l; len <= n; ++len) {
    long long L = (l + len + 1) / 2;
    long long R = min(len, (r + len) / 2);
    if (L > R) continue;
    (ans += (long long)c(n, len) * (c(len, L) + p - c(len, R + 1))) %= p;
  }
  cout << ans << endl;
}
