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;
int n, l, r;
long long mod;
vector<int> primes;
vector<long long> powPrime, modFact[100000 + 1];
long long modPow(long long a, long long pow, long long m) {
  if (pow == 0) return 1;
  if (pow & 1)
    return (a * modPow(a, pow ^ 1, m)) % m;
  else {
    long long sqrt = modPow(a, pow >> 1, m);
    return (sqrt * sqrt) % m;
  }
}
int numFactorsInFact(int fact, int prime) {
  int res = 0;
  while (fact > 0) {
    fact /= prime;
    res += fact;
  }
  return res;
}
long long inverseInPrimePowMod(int a, int prime) {
  return modPow(a, powPrime[prime] / primes[prime] * (primes[prime] - 1) - 1,
                powPrime[prime]);
}
long long getBaseFactModWithoutPrime(int fact, int prime) {
  long long res = 1;
  while (fact > 0) {
    res *= modFact[fact][prime];
    res %= powPrime[prime];
    fact /= primes[prime];
  }
  return res;
}
long long C(int a, int b) {
  if (b < 0 || b > a) return 0;
  if (a == 0) return 1;
  long long curr = 0;
  long long base = 1;
  for (int i = 0; i < (primes.size()); i++) {
    int af = numFactorsInFact(a, primes[i]);
    int bf = numFactorsInFact(b, primes[i]);
    int cf = numFactorsInFact(a - b, primes[i]);
    long long aa = getBaseFactModWithoutPrime(a, i);
    long long bb = getBaseFactModWithoutPrime(b, i);
    long long cc = getBaseFactModWithoutPrime(a - b, i);
    long long c = modPow(primes[i], af - bf - cf, powPrime[i]);
    c *= aa;
    c %= powPrime[i];
    c *= inverseInPrimePowMod(bb, i);
    c %= powPrime[i];
    c *= inverseInPrimePowMod(cc, i);
    c %= powPrime[i];
    curr += base * (c - curr) * inverseInPrimePowMod(base, i);
    base *= powPrime[i];
    curr %= base;
    curr += base;
    curr %= base;
  }
  return curr;
}
long long solve(int a, int lo, int hi) {
  if (a & 1) {
    return (solve(a - 1, lo - 1, hi - 1) + solve(a - 1, lo + 1, hi + 1)) % mod;
  } else {
    lo = (lo + 1) / 2;
    hi >>= 1;
    if (lo > hi) return 0;
    return ((C(a, a / 2 + lo) - C(a, a / 2 + hi + 1)) % mod + mod) % mod;
  }
}
void calculateMods(long long i, long long m) {
  long long curr = 1;
  for (int j = 0; j < (100000 + 1); j++) {
    if (j % i != 0) {
      curr *= j;
      curr %= m;
    }
    modFact[j].push_back(curr);
  }
}
void findFactors() {
  long long tmod = mod;
  for (long long i = 2; i * i <= tmod; i++) {
    if (tmod % i == 0) {
      primes.push_back((int)i);
      powPrime.push_back(1);
    } else
      continue;
    while (tmod % i == 0) {
      tmod /= i;
      powPrime[powPrime.size() - 1] *= i;
    }
    calculateMods(i, powPrime[powPrime.size() - 1]);
  }
  if (tmod > 1) {
    primes.push_back(tmod);
    powPrime.push_back(tmod);
    calculateMods(tmod, tmod);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> mod >> l >> r;
  findFactors();
  long long res = 0;
  for (int vips = 0; vips < (n + 1); vips++) {
    res += (C(n, vips) * solve(n - vips, l, r)) % mod;
    res %= mod;
  }
  cout << res << endl;
  return 0;
}
