← 返回题目列表

Codeforces · 896/D

D. Nephren 经营一家电影院

中文机器翻译题面 查看原题

Lakhesh 喜欢拍电影,所以 Nephren 帮助她经营一家电影院。我们可以称之为68号电影院。

然而有一天,68号电影院的零钱用完了(目前没有50元纸币),但尼弗伦仍然想创业。 (假设人民币是Regulu Ere中的一种货币。)

顾客分为三类:有的正好带了一张50元纸币;有的拿着50元纸币。有的人带了100元的纸币,Nephren需要还给他/她一张50元的纸币;有些人带着VIP卡,这样就不用买票了。

现在有n个顾客在外面排队等候。 Nephren想知道有多少个可能的队列,他们能够顺利运行(即每个顾客都能收到他/她的零钱),并且在向所有这些顾客售票后,他们拥有的50元纸币的数量在l和r之间(含)。如果两个队列中存在类型不同的顾客,则认为两个队列不同。由于数字可能很大,请输出对 p 取模的答案。

输入

一行包含四个整数 n (1 ≤ n ≤ 105)、p (1 ≤ p ≤ 2·109)、l 和 r (0 ≤ l ≤ r ≤ n)。

输出

一行指示以 p 为模的答案。

示例

输入 #1

4 97 2 3

输出 #1

13

输入 #2

4 100 0 4

输出 #2

35

注意

我们用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 个不同的队列满足第二个样本。