Problem: 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.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long int inf = 1000000000;
const long long int mod = 1000000000 + 7;
inline void IO() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
inline int dcmp(long double x) { return x < -1e-12 ? -1 : (x > 1e-12); }
template <class T>
inline int CHECK(T MASK, int i) {
  return (MASK >> i) & 1;
}
template <class T>
inline T ON(T MASK, int i) {
  return MASK | (T(1) << i);
}
template <class T>
inline T OFF(T MASK, int i) {
  return MASK & (~(T(1) << i));
}
template <typename T>
inline int CNT(T MASK) {
  if (numeric_limits<T>::digits <= numeric_limits<unsigned int>::digits)
    return __builtin_popcount(MASK);
  else
    return __builtin_popcountll(MASK);
}
template <class T>
inline int RIGHT(T MASK) {
  return log2(MASK & -MASK);
}
int dx4[] = {0, 0, -1, +1};
int dy4[] = {+1, -1, 0, 0};
int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1, 0};
int dy8[] = {0, 1, 1, 1, 0, -1, -1, -1, 0};
inline void I(int& a) { scanf("%d", &a); }
inline void I(long long int& a) { scanf("%I64d", &a); }
inline void I(unsigned long long int& a) { scanf("%I64u", &a); }
inline void I(char* a) { scanf("%s", a); }
char Iarr[2000010];
inline void I(string& a) {
  scanf("%s", Iarr);
  a = Iarr;
}
template <typename T, typename... Args>
void I(T& a, Args&... args) {
  I(a);
  I(args...);
}
inline void OUT(int a) { printf("%d", a); }
inline void OUT(long long int a) { printf("%I64d", a); }
inline void OUT(const char* a) { printf("%s", a); }
inline void OUT(char* a) { printf("%s", a); }
inline void OUT(bool a) { printf("%d", a); }
inline void OUT(string a) {
  for (__typeof(a.end()) it = (a.begin()) - ((a.begin()) > (a.end()));
       it != (a.end()) - ((a.begin()) > (a.end()));
       it += 1 - 2 * ((a.begin()) > (a.end())))
    printf("%c", *it);
}
inline void OUT(unsigned long long int a) { printf("%I64u", a); }
template <typename T, typename... Args>
void OUT(T a, Args... args) {
  OUT(a);
  OUT(" ");
  OUT(args...);
}
template <typename... Args>
void O(Args... args) {
  OUT(args...);
  OUT("\n");
}
template <typename T1, typename T2>
inline ostream& operator<<(ostream& os, pair<T1, T2> p) {
  os << "{" << p.first << ", " << p.second << "}";
  return os;
}
template <typename T>
inline ostream& operator<<(ostream& os, vector<T>& a) {
  os << "[";
  for (int i = 0; i < (int)a.size(); i++) {
    if (i) os << ", ";
    os << a[i];
  }
  os << "]";
  return os;
}
void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cout << *it << " = " << a << endl;
  err(++it, args...);
}
const int M = 200010;
struct NCRMOD {
  int n, MOD, PHI, residue[100001], fact[100001], inv_fact[100001];
  vector<int> primeDivisors;
  vector<vector<int> > C, P;
  int ModExp(int a, int n) {
    long long x = a % MOD, y = 1 % MOD;
    while (n) {
      if (n % 2) y = (x * y) % MOD;
      x = (x * x) % MOD;
      n /= 2;
    }
    return (int)y;
  }
  int ModInv(int a) { return ModExp(a, PHI - 1); }
  void PreProcess() {
    int m = MOD;
    for (int i = 2; i * i <= m; ++i) {
      if (m % i == 0) {
        while (m % i == 0) m /= i;
        primeDivisors.push_back(i);
      }
    }
    if (m > 1) primeDivisors.push_back(m);
    m = primeDivisors.size();
    C.resize(m);
    P.resize(m);
    fact[0] = 1, inv_fact[0] = 1;
    for (int i = 1; i <= n; ++i) residue[i] = i;
    PHI = MOD;
    for (int i = 0; i < m; ++i) {
      int p = primeDivisors[i];
      PHI /= p;
      PHI *= (p - 1);
      C[i].resize(n + 1);
      for (int j = p; j <= n; j += p) {
        int x = residue[j], k = 0;
        while (x % p == 0) {
          x /= p;
          ++k;
        }
        residue[j] = x;
        C[i][j] = k;
      }
      for (int j = 1; j <= n; ++j) C[i][j] += C[i][j - 1];
      P[i].resize(C[i][n] + 1);
      P[i][0] = 1 % MOD;
      for (int j = 1; j < P[i].size(); ++j)
        P[i][j] = (1ll * p * P[i][j - 1]) % MOD;
    }
    for (int i = 1; i <= n; ++i)
      fact[i] = (1ll * residue[i] * fact[i - 1]) % MOD;
    inv_fact[n] = ModInv(fact[n]);
    for (int i = n - 1; i > 0; --i)
      inv_fact[i] = (1ll * residue[i + 1] * inv_fact[i + 1]) % MOD;
  }
  int NCR(int n, int r) {
    if (n < 0 || r < 0 || n < r)
      return 0;
    else {
      long long ans = fact[n];
      ans = (ans * inv_fact[r]) % MOD;
      ans = (ans * inv_fact[n - r]) % MOD;
      for (int i = 0; i < primeDivisors.size(); ++i) {
        int c = C[i][n] - C[i][r] - C[i][n - r];
        ans = (ans * P[i][c]) % MOD;
      }
      return (int)ans;
    }
  }
} obj;
long long int func(long long int n, long long int sum, long long int MOD) {
  long long int ret;
  if (n % 2 == 0)
    ret = obj.NCR(n, n / 2) - obj.NCR(n, n / 2 + sum / 2 + 1);
  else {
    if (sum % 2 == 0)
      ret = obj.NCR(n, n / 2) - obj.NCR(n, n / 2 - sum / 2);
    else
      ret = obj.NCR(n, n / 2) - obj.NCR(n, n / 2 - sum / 2 - 1);
  }
  return ret;
}
long long int range(long long int n, long long int l, long long int r,
                    long long int MOD) {
  long long int ret = func(n, r, MOD);
  if (l > 0) ret -= func(n, l - 1, MOD);
  ret %= MOD;
  ret = (ret + MOD) % MOD;
  return ret;
}
int main() {
  long long int n, p, l, r;
  I(n, p, l, r);
  obj.MOD = p;
  obj.n = n;
  obj.PreProcess();
  long long int ans = 0;
  for (long long int i = l; i <= n; i++) {
    long long int temp = obj.NCR(n, i);
    temp %= p;
    temp *= range(i, l, r, p);
    temp %= p;
    ans += temp;
    ans %= p;
  }
  O(ans);
  return 0;
}