Nephren Runs 영화관

Lakhesh는 영화 만드는 것을 좋아해서, Nephren은 그녀가 영화관을 운영하는 것을 돕는다. 이곳을 No. 68 Cinema라고 부르기로 하자.

하지만 어느 날 No. 68 Cinema에는 거스름돈이 떨어졌고(현재 50위안 지폐가 없다), 그래도 Nephren은 영업을 시작하려 한다. (위안은 Regulu Ere에서 사용하는 화폐의 일종이라고 가정한다.)

손님은 세 유형이다. 일부는 정확히 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로 나눈 나머지를 출력한다.

A, B and C는 각각 50위안 지폐를 가진 손님, 100위안 지폐를 가진 손님, VIP 카드를 가진 손님을 나타내는 데 사용한다.

첫 번째 예제에서 50위안 지폐가 2장 남는 서로 다른 가능한 줄은 AAAB, AABA, ABAA, AACC, ACAC, ACCA, CAAC, CACA and CCAA이고, 50위안 지폐가 3장 남는 서로 다른 가능한 줄은 AAAC, AACA, ACAA and CAAA이다. 따라서 첫 번째 예제를 만족하는 서로 다른 줄은 13개이다. 마찬가지로 두 번째 예제를 만족하는 서로 다른 줄은 35개이다.