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;
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int &x, int y, int mod = 1000000007) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et() {
  puts("-1");
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 1000000007) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) {
  long long z = y;
  while (x % y != 0) {
    z = x % y;
    x = y;
    y = z;
  }
  return z;
}
long long phi(long long x) {
  long long ans = x;
  for (long long i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      ans = ans / i * (i - 1);
      while (x % i == 0) x /= i;
    }
  }
  if (x > 1) ans = ans / x * (x - 1);
  return ans;
}
int fac[100005], inv[100005], tc[100005][20];
vector<int> ps;
void initfac(int n, int P) {
  int tmp = P;
  for (int i = 2; (long long)i * i <= tmp; i++)
    if (tmp % i == 0) {
      while (tmp % i == 0) tmp /= i;
      ps.push_back(i);
    }
  if (tmp > 1) ps.push_back(tmp);
  fac[0] = inv[0] = 1;
  fac[1] = inv[1] = 1;
  int N = ps.size();
  long long Phi = phi(P);
  for (int i = 2; i <= n; i++) {
    tmp = i;
    for (int(j) = 0; (j) < (int)(N); (j)++) {
      tc[i][j] += tc[i - 1][j];
      if (tmp % ps[j] != 0) continue;
      while (tmp % ps[j] == 0) {
        tmp /= ps[j];
        tc[i][j]++;
      }
    }
    fac[i] = (long long)fac[i - 1] * tmp % P;
    inv[i] = fastPow(fac[i], Phi - 1, P);
  }
}
int C(int n, int m, int P) {
  if (n < m) return 0;
  if (m == 0) return 1;
  int ans = (long long)fac[n] * inv[m] % P * inv[n - m] % P;
  for (int(i) = 0; (i) < (int)(ps.size()); (i)++) {
    ans = (long long)ans *
          fastPow(ps[i], tc[n][i] - tc[m][i] - tc[n - m][i], P) % P;
  }
  return ans;
}
void fmain(int ID) {
  int n, p, l, r;
  scanf("%d%d%d%d", &n, &p, &l, &r);
  long long ans = 0;
  initfac(n, p);
  for (int i = 0; i <= n; i++) {
    int tn = n - i;
    int gg = C(n, i, p);
    int R = min(tn, r);
    if (R < l) continue;
    long long tmp = -C(tn, (tn + R) / 2 + 1, p) + C(tn, (tn + l + 1) / 2, p);
    tmp = (tmp + p) % p;
    ans += (long long)gg * tmp % p;
    ans %= p;
  }
  printf("%lld\n", ans);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}
