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