English · Original
Chinese · Translation
Formal · Original
Lakhesh loves to make movies, so Nephren helps her run a cinema. We may call it No. 68 Cinema.
<center>
</center>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_.
[samples]
## 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.
Lakhesh 热爱制作电影，因此 Nephren 帮助她经营一家电影院。我们可以称它为第 68 电影院。
然而，有一天，第 68 电影院用完了零钱（他们目前没有 50-_yuan_ 纸币），但 Nephren 仍希望开始他们的生意。（假设 _yuan_ 是 Regulu Ere 地区的一种货币。）
有三种类型的顾客：一些人恰好带来一张 50-_yuan_ 纸币；一些人带来一张 100-_yuan_ 纸币，此时 Nephren 需要找回一张 50-_yuan_ 纸币给他/她；还有一些人持有 VIP 卡，因此他们无需支付票款。
现在有 #cf_span[n] 位顾客在门外排队。Nephren 希望知道有多少种可能的排队方式，使得他们能够顺利运营（即每位顾客都能收到应找的零钱），并且在售完所有这些顾客的票后，他们拥有的 50-_yuan_ 纸币数量介于 #cf_span[l] 和 #cf_span[r] 之间（包含两端）。两个队列被认为是不同的，如果存在至少一位顾客在两个队列中的类型不同。由于答案可能很大，请输出答案对 #cf_span[p] 取模的结果。
输入一行包含四个整数：#cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]）、#cf_span[p]（#cf_span[1 ≤ p ≤ 2·10^9]）、#cf_span[l] 和 #cf_span[r]（#cf_span[0 ≤ l ≤ r ≤ n]）。
输出一行，表示答案对 #cf_span[p] 取模的结果。
我们用 A、B 和 C 分别表示携带 50-_yuan_ 纸币的顾客、携带 100-_yuan_ 纸币的顾客和持有 VIP 卡的顾客。
对于第一个样例，剩余 2 张 50-_yuan_ 纸币的可能队列有：AAAB、AABA、ABAA、AACC、ACAC、ACCA、CAAC、CACA 和 CCAA；剩余 3 张 50-_yuan_ 纸币的可能队列有：AAAC、AACA、ACAA 和 CAAA。因此共有 #cf_span[13] 种满足第一个样例的队列。类似地，满足第二个样例的队列有 #cf_span[35] 种。
## Input
输入一行包含四个整数：#cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]）、#cf_span[p]（#cf_span[1 ≤ p ≤ 2·10^9]）、#cf_span[l] 和 #cf_span[r]（#cf_span[0 ≤ l ≤ r ≤ n]）。
## Output
输出一行，表示答案对 #cf_span[p] 取模的结果。
[samples]
## Note
我们用 A、B 和 C 分别表示携带 50-_yuan_ 纸币的顾客、携带 100-_yuan_ 纸币的顾客和持有 VIP 卡的顾客。对于第一个样例，剩余 2 张 50-_yuan_ 纸币的可能队列有：AAAB、AABA、ABAA、AACC、ACAC、ACCA、CAAC、CACA 和 CCAA；剩余 3 张 50-_yuan_ 纸币的可能队列有：AAAC、AACA、ACAA 和 CAAA。因此共有 #cf_span[13] 种满足第一个样例的队列。类似地，满足第二个样例的队列有 #cf_span[35] 种。
**Definitions**
Let $ n, p, l, r \in \mathbb{Z} $ with $ 1 \leq n \leq 10^5 $, $ 1 \leq p \leq 2 \cdot 10^9 $, and $ 0 \leq l \leq r \leq n $.
Let the customer types be:
- Type A: pays 50 yuan (increases 50-yuan note count by 1),
- Type B: pays 100 yuan (requires one 50-yuan note as change, decreases count by 1),
- Type C: uses VIP card (no change required, count unchanged).
Let a queue be a sequence $ Q \in \{A, B, C\}^n $.
Let $ f(Q) $ be the number of 50-yuan notes remaining after processing $ Q $, starting from 0 notes, with the constraint that the count never drops below 0 (i.e., at any prefix, number of A’s ≥ number of B’s).
**Constraints**
1. For any prefix of $ Q $, the number of A’s ≥ number of B’s.
2. $ f(Q) \in [l, r] $.
**Objective**
Compute the number of valid queues $ Q \in \{A, B, C\}^n $ satisfying the above constraints, modulo $ p $.
API Response (JSON)
{
"problem": {
"name": "D. Nephren Runs a Cinema",
"description": {
"content": "Lakhesh loves to make movies, so Nephren helps her run a cinema. We may call it No. 68 Cinema. <center> </center",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF896D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Lakhesh loves to make movies, so Nephren helps her run a cinema. We may call it No. 68 Cinema.\n\n<center>\n\n</center...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Lakhesh 热爱制作电影，因此 Nephren 帮助她经营一家电影院。我们可以称它为第 68 电影院。\n\n然而，有一天，第 68 电影院用完了零钱（他们目前没有 50-_yuan_ 纸币），但 Nephren 仍希望开始他们的生意。（假设 _yuan_ 是 Regulu Ere 地区的一种货币。）\n\n有三种类型的顾客：一些人恰好带来一张 50-_yuan_ 纸币；一些人带来一张 100-_yu...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, p, l, r \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 10^5 $, $ 1 \\leq p \\leq 2 \\cdot 10^9 $, and $ 0 \\leq l \\leq r \\leq n $. \nLet the customer types be: \n- Type A: pays 50 yuan (...",
"is_translate": false,
"language": "Formal"
}
]
}