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 comment(linker, "/STACK:108777216")
using namespace std;
int const MAX_N = 105 * 1024;
void ad(long long& x, long long val, long long p) { x = (x + val) % p; }
using namespace std;
const int inf = 1010000000;
const double eps = 1e-9;
long long p[111];
int pp = 0;
long long P;
struct num {
  vector<int> a;
  long long r;
  num(long long x) {
    a = vector<int>(pp);
    for (int i = 0; (i) < (pp); ++i) {
      while (x % p[i] == 0) {
        a[i]++;
        x /= p[i];
      }
    }
    r = x;
  }
  num() {
    a = vector<int>(pp);
    r = 0;
  }
};
inline num operator*(num A, num B) {
  num C;
  for (int i = 0; (i) < (pp); ++i) C.a[i] = A.a[i] + B.a[i];
  C.r = A.r * (long long)B.r % P;
  return C;
}
long long rev(long long a, long long m) {
  if (a == 1) return 1;
  return (1 - rev(m % a, a) * (long long)m) / a + m;
}
inline num operator/(num A, num B) {
  num C;
  for (int i = 0; (i) < (pp); ++i) C.a[i] = A.a[i] - B.a[i];
  C.r = A.r * (long long)rev(B.r, P) % P;
  return C;
}
num fact[MAX_N];
void init() {
  long long mod = P;
  for (int i = 2; i * i <= mod; ++i)
    if (mod % i == 0) {
      p[pp++] = i;
      while (mod % i == 0) mod /= i;
    }
  if (mod > 1) p[pp++] = mod;
  fact[0] = num(1);
  for (int i = 1; i < MAX_N; ++i) {
    fact[i] = fact[i - 1] * num(i);
  }
}
long long cnk(long long n, long long k) {
  if (k > n || k < 0) return 0;
  if (k == 0 || k == n) return 1 % P;
  num R = fact[n] / (fact[k] * fact[n - k]);
  long long ans = R.r;
  for (int i = 0; (i) < (pp); ++i)
    for (int j = 0; (j) < (R.a[i]); ++j) ans = (ans * (long long)p[i]) % P;
  return ans;
}
long long f2_UP(long long n, long long p, long long up_k) {
  long long UP = 0;
  for (long long x = n; x >= n - up_k; x--) {
    long long df = up_k + x - n;
    long long i = df / 2;
    if (i >= 0) ad(UP, cnk(x, i) % p * cnk(n, x) % p, p);
  }
  return UP;
}
long long f2(long long n, long long p, long long RRR) {
  long long XX = f2_UP(n, P, n) - f2_UP(n, P, n - RRR - 1);
  XX = ((XX % P) + P) % P;
  return XX;
}
int main() {
  int n, l, r;
  cin >> n >> P >> l >> r;
  init();
  if (P <= 1) {
    cout << "0";
    return 0;
  }
  long long A = f2(n, P, r);
  long long B = f2(n, P, l - 1);
  long long res = ((A - B) % P + ((long long)P)) % P;
  cout << res;
  return 0;
}
