{"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>![image](https://espresso.codeforces.com/392e1a3786d67668df6910801bb5d9e188ec8f54.png) </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>![image](https://espresso.codeforces.com/392e1a3786d67668df6910801bb5d9e188ec8f54.png)\n\n</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.)\n\nThere 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.\n\nNow _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_.\n\n## Input\n\nOne line containing four integers _n_ (1 ≤ _n_ ≤ 105), _p_ (1 ≤ _p_ ≤ 2·109), _l_ and _r_ (0 ≤ _l_ ≤ _r_ ≤ _n_).\n\n## Output\n\nOne line indicating the answer modulo _p_.\n\n[samples]\n\n## Note\n\nWe use A, B and C to indicate customers with 50-_yuan_ notes, customers with 100-_yuan_ notes and customers with VIP cards respectively.\n\nFor 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.","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-_yuan_ 纸币，此时 Nephren 需要找回一张 50-_yuan_ 纸币给他/她；还有一些人持有 VIP 卡，因此他们无需支付票款。\n\n现在有 #cf_span[n] 位顾客在门外排队。Nephren 希望知道有多少种可能的排队方式，使得他们能够顺利运营（即每位顾客都能收到应找的零钱），并且在售完所有这些顾客的票后，他们拥有的 50-_yuan_ 纸币数量介于 #cf_span[l] 和 #cf_span[r] 之间（包含两端）。两个队列被认为是不同的，如果存在至少一位顾客在两个队列中的类型不同。由于答案可能很大，请输出答案对 #cf_span[p] 取模的结果。\n\n输入一行包含四个整数：#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]）。\n\n输出一行，表示答案对 #cf_span[p] 取模的结果。\n\n我们用 A、B 和 C 分别表示携带 50-_yuan_ 纸币的顾客、携带 100-_yuan_ 纸币的顾客和持有 VIP 卡的顾客。\n\n对于第一个样例，剩余 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] 种。\n\n## Input\n\n输入一行包含四个整数：#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]）。\n\n## Output\n\n输出一行，表示答案对 #cf_span[p] 取模的结果。\n\n[samples]\n\n## Note\n\n我们用 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] 种。","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 (increases 50-yuan note count by 1),  \n- Type B: pays 100 yuan (requires one 50-yuan note as change, decreases count by 1),  \n- Type C: uses VIP card (no change required, count unchanged).  \n\nLet a queue be a sequence $ Q \\in \\{A, B, C\\}^n $.  \n\nLet $ 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).  \n\n**Constraints**  \n1. For any prefix of $ Q $, the number of A’s ≥ number of B’s.  \n2. $ f(Q) \\in [l, r] $.  \n\n**Objective**  \nCompute the number of valid queues $ Q \\in \\{A, B, C\\}^n $ satisfying the above constraints, modulo $ p $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF896D","tags":["chinese remainder theorem","combinatorics","math","number theory"],"sample_group":[["4 97 2 3","13"],["4 100 0 4","35"]],"created_at":"2026-03-03 11:00:39"}}