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>
#pragma GCC optimize("-O3")
using namespace std;
void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  _main();
}
const int inf = INT_MAX / 2;
const long long infl = 1LL << 60;
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
struct SuperCombination2 {
  int mod, n, tot;
  vector<long long> inv, fac, p;
  vector<vector<long long>> t;
  int isinit = 0;
  int phi(int k) {
    int i, s;
    s = k;
    for (i = 2; i * i <= k; i++) {
      if (k % i == 0) s = s / i * (i - 1);
      while (k % i == 0) k /= i;
    }
    if (k > 1) s = s / k * (k - 1);
    return s;
  }
  long long qpow(long long a, long long b) {
    long long res = 1;
    while (b) {
      if (b & 1) res = res * a % mod;
      b >>= 1;
      a = a * a % mod;
    }
    return res;
  }
  void init(int _n, int _mod) {
    mod = _mod;
    n = _n + 5;
    tot = 0;
    inv.resize(n);
    fac.resize(n);
    p.resize(n);
    t.resize(n, vector<long long>(20));
    long long x = mod;
    int Phi = phi(mod);
    for (int i = 2; (long long)i * i <= x; i++) {
      if (x % i) continue;
      while (x % i == 0) x /= i;
      p[++tot] = i;
    }
    if (x > 1) p[++tot] = x;
    inv[0] = inv[1] = 1;
    fac[0] = fac[1] = 1;
    for (int i = 2; i < n; i++) {
      x = i;
      for (int j = 1; j <= tot; j++) {
        t[i][j] = t[i - 1][j];
        if (x % p[j]) continue;
        while (x % p[j] == 0) x /= p[j], t[i][j]++;
      }
      fac[i] = fac[i - 1] * x % mod;
      inv[i] = qpow(fac[i], Phi - 1);
    }
    isinit = 1;
  }
  long long C(int n, int m) {
    assert(isinit == 1 && "Please init!!");
    long long res = 0;
    if (n < m) return 0;
    if (m == 0) return 1;
    res = fac[n] * inv[m] % mod * inv[n - m] % mod;
    for (int i = 1; i <= tot; i++)
      res = res * qpow(p[i], t[n][i] - t[m][i] - t[n - m][i]) % mod;
    return res;
  }
};
int N, P, L, R;
void _main() {
  cin >> N >> P >> L >> R;
  SuperCombination2 sc;
  sc.init(N, P);
  long long ans = 0;
  for (int i = 0; i < N + 1; i++) {
    int m = N - i;
    long long d =
        (-sc.C(m, (m + min(R, m) >> 1) + 1) + sc.C(m, m + L + 1 >> 1)) % P;
    ans += sc.C(N, i) * d;
    ans %= P;
  }
  cout << ans << endl;
}
