CF896D Nephren Runs a Cinema

Lakhesh 喜欢拍电影，所以 Nephren 帮助她经营一家电影院。我们可以称之为 No. 68 电影院。  然而有一天，No. 68 电影院用光了找零（他们现在没有 50 元的纸币了），但 Nephren 仍然想要营业。（假设「元」是一种 Regulu Ere 的货币。） 顾客有三种类型：有的顾客带着恰好一张 50 元纸币，有的带着一张 100 元纸币，Nephren 需要找给他/她一张 50 元纸币；还有的拿着 VIP 卡，他们不用为门票付钱。 现在有 $ n $ 位顾客在门外排队。Nephren 想知道，有多少种可能的排队顺序，可以让电影院顺利营业（即每位顾客都能收到应得的找零），并且在所有顾客购票完毕后，影院剩余的 50 元纸币数量在 $ l $ 到 $ r $ 之间（包含 $ l $ 和 $ r $）。如果存在某个顾客在两队中类型不同，则认为这两个排队队列是不同的。由于方案数可能很大，请输出答案对 $ p $ 取模。

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

输出一行，表示方案数对 $ p $ 取模的结果。

我们用 $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$ 种。 由 ChatGPT 5 翻译