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;
struct NTT {
  int p, g, m;
  static int quick_power(int n, int i, int p) {
    long long r = 1;
    for (; i; i >>= 1, n = 1LL * n * n % p) (i & 1) && (r = r * n % p);
    return r;
  }
  NTT() {}
  NTT(int p, int g) { this->p = p, this->g = g, m = 0; }
  void FFT(int *arr, int n, bool forth) const {
    static int ww[300000];
    assert((p - 1) % n == 0);
    long long gg = quick_power(g, (p - 1) / n, p);
    ww[0] = ww[n] = 1;
    if (forth)
      for (int i = 1; i < n; i++) ww[i] = ww[i - 1] * gg % p;
    else
      for (int i = n - 1; i >= 0; i--) ww[i] = ww[i + 1] * gg % p;
    for (int i = 1, j = n >> 1, k, l = j; i < n; j ^= k, i++) {
      if (i < j) swap(arr[i], arr[j]);
      for (k = l; k & j; j ^= k, k >>= 1)
        ;
    }
    for (int i = 1; i < n; i <<= 1)
      for (int ii = i << 1, ni = n / ii, j = 0; j < n; j += ii)
        for (int k = 0, *xx = &arr[j], *w = ww, x, y; k < i;
             k++, xx++, w += ni) {
          x = *xx, y = (long long)xx[i] * (*w) % p;
          *xx = ((long long)x + y) % p, xx[i] = ((long long)x + p - y) % p;
        }
    if (!forth)
      for (int i = 0, ninv = quick_power(n, p - 2, p); i < n; i++)
        arr[i] = (long long)arr[i] * ninv % p;
  }
  void multiply(int *arr, int n, const int *other) const {
    for (int i = 0; i < n; i++) arr[i] = (long long)arr[i] * other[i] % p;
  }
  void power(int *arr, int n, int xp) const {
    static int art[300000];
    if (xp == 0)
      for (int i = 0; i < n; i++) arr[i] = 1 % p;
    else if ((xp & 1) == 1) {
      memcpy(art, arr, n * sizeof(int));
      power(arr, n, xp >> 1);
      for (int i = 0; i < n; i++)
        arr[i] = (long long)arr[i] * arr[i] % p * art[i] % p;
    } else {
      power(arr, n, xp >> 1);
      for (int i = 0; i < n; i++) arr[i] = (long long)arr[i] * arr[i] % p;
    }
  }
};
struct ANTT {
  const int pp[3] = {998244353, 1004535809, 469762049}, gg[3] = {3, 3, 3};
  const long long p01 = (long long)pp[0] * pp[1];
  static const int np = 3, nl = 11;
  int p, pinv[3];
  long long *pxinv;
  NTT ntt[3];
  ANTT(int p) {
    this->p = p;
    memset(ntt, 0, sizeof(ntt));
    for (int i = 0; i < np; i++) ntt[i] = NTT(pp[i], gg[i]);
    pinv[0] = NTT::quick_power(pp[0] % pp[1], pp[1] - 2, pp[1]);
    pinv[1] = NTT::quick_power(pp[1] % pp[0], pp[0] - 2, pp[0]);
    pinv[2] = NTT::quick_power(p01 % pp[2], pp[2] - 2, pp[2]);
    pxinv = (long long *)malloc((nl * 2) * sizeof(long long));
    pxinv[0] = (long long)pp[0] * pinv[0],
    pxinv[nl] = (long long)pp[1] * pinv[1];
    for (int l = 1; l < nl; l++)
      pxinv[l] = (pxinv[l - 1] << 3) % p01,
      pxinv[nl + l] = (pxinv[nl + l - 1] << 3) % p01;
  }
  ~ANTT() { free(pxinv); }
  int CRT(int a0, int a1, int a2) const {
    long long x = 0;
    for (int l = nl; a0 != 0; l++, a0 >>= 3)
      x = (x + (a0 & 7) * pxinv[l]) % p01;
    for (int l = 0; a1 != 0; l++, a1 >>= 3) x = (x + (a1 & 7) * pxinv[l]) % p01;
    long long k = ((long long)a2 + pp[2] - x % pp[2]) * pinv[2] % pp[2];
    return (k * (p01 % p) + x) % p;
  }
  void FFT(int *arx, int n, bool forth) const {
    for (int i = 0; i < np; i++) ntt[i].FFT(&arx[i * n], n, forth);
  }
  void multiply(int *arx, int n, const int *other) const {
    for (int i = 0; i < np; i++) ntt[i].multiply(&arx[i * n], n, &other[i * n]);
  }
  void power(int *arx, int n, int xp) const {
    for (int i = 0; i < np; i++) ntt[i].power(&arx[i * n], n, xp);
  }
  void pre(const int *arr, int n, int *arx) const {
    for (int i = 0; i < np; i++) memcpy(&arx[i * n], arr, n * sizeof(int));
  }
  void post(int *arr, int n, const int *arx) const {
    for (int i = 0; i < n; i++)
      arr[i] = CRT(arx[i], arx[n + i], arx[n + n + i]);
  }
};
void power_raw(const ANTT &antt, int *arr, int xp) {
  int n = (xp << 1) + 1, nn = 1;
  while (nn < n) nn <<= 1;
  if (xp <= 45) {
    int arx[3 * nn];
    antt.pre(arr, nn, arx), antt.FFT(arx, nn, true);
    antt.power(arx, nn, xp);
    antt.FFT(arx, nn, false), antt.post(arr, nn, arx);
  } else {
    int arx[3 * nn], atx[3 * nn];
    if (xp & 1) antt.pre(arr, nn, atx), antt.FFT(atx, nn, true);
    power_raw(antt, arr, xp >> 1);
    antt.pre(arr, nn, arx), antt.FFT(arx, nn, true);
    antt.multiply(arx, nn, arx);
    if (xp & 1) antt.multiply(arx, nn, atx);
    antt.FFT(arx, nn, false), antt.post(arr, nn, arx);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, p, l, r, nn = 1;
  cin >> n >> p >> l >> r;
  while (nn < 2 * n + 3) nn <<= 1;
  int x[nn];
  memset(x, 0, nn * sizeof(int));
  x[0] = x[1] = x[2] = 1 % p;
  ANTT antt(p);
  power_raw(antt, x, n);
  long long xx =
      ((long long)x[n + l] + x[n + l + 1] - x[n + r + 1] - x[n + r + 2]) % p;
  cout << (xx + p) % p << endl;
  return 0;
}