CF896D.Nephren Runs a Cinema

Lakhesh loves to make movies, so Nephren helps her run a cinema. We may call it No. 68 Cinema.

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.

拉克什热爱拍电影，因此奈芙伦帮她经营一家电影院。我们可以称它为68号电影院。

然而某天，68号电影院用完了找零（目前没有50元纸币），但奈芙伦仍希望照常营业。（假设“元”是雷古鲁·艾尔地区的一种货币单位。）

顾客共有三类：一部分顾客恰好携带一张50元纸币；一部分顾客携带一张100元纸币，奈芙伦需找还一张50元纸币；还有一部分顾客持有VIP卡，无需支付门票费用。

现在有 $ n $ 名顾客在门外排成一队。奈芙伦想知道：有多少种可能的排队方式，使得整个售票过程能顺利进行（即每位顾客均能及时获得所需找零），且在向所有顾客售完票后，影院所剩余的50元纸币数量在 $ l $ 到 $ r $ 之间（含端点）。若两支队伍中存在某位顾客的类型不同，则认为这两支队伍不同。由于答案可能很大，请输出其对 $ p $ 取模的结果。

One line containing four integers n (1 ≤ n ≤ 105), p (1 ≤ p ≤ 2·109), l and r (0 ≤ l ≤ r ≤ n).

一行包含四个整数 $n$（$1 ≤ n ≤ 10^5$）、$p$（$1 ≤ p ≤ 2·10^9$）、$l$ 和 $r$（$0 ≤ l ≤ r ≤ n$）。

One line indicating the answer modulo p.

一行，表示答案对 $p$ 取模的结果。

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.

我们用 A、B 和 C 分别表示持有 50 元纸币的顾客、持有 100 元纸币的顾客以及持有 VIP 卡的顾客。

对于第一个样例，剩余 2 张 50 元纸币的所有可能队列有：AAAB、AABA、ABAA、AACC、ACAC、ACCA、CAAC、CACA 和 CCAA；剩余 3 张 50 元纸币的所有可能队列有：AAAC、AACA、ACAA 和 CAAA。因此，满足第一个样例的队列共有 13 种。类似地，满足第二个样例的队列共有 35 种。