Nephren Runs a Cinema
Contest: Codeforces Round 449 (Div. 1)
Difficulty rating: 2900
Tags: chinese remainder theorem, combinatorics, math, number theory

Lakhesh loves to make movies, so Nephren helps her run a cinema. We may call it No. 68 Cinema.

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.)

There 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.

Now 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.

Input format:
One line containing four integers n (1 ≤ n ≤ 105), p (1 ≤ p ≤ 2·109), l and r (0 ≤ l ≤ r ≤ n).

Output format:
One line indicating the answer modulo p.

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

Note:
We use A, B and C to indicate customers with 50-yuan notes, customers with 100-yuan notes and customers with VIP cards respectively.

For 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.

Example input:
4 97 2 3

Example output:
13

Example input:
4 100 0 4

Example output:
35

Editorial:
First let's consider if there are no customers with VIP cards and there are no 50-yuan notes left. By defining points (number of customers received, number of 50-yuan note left) on a 2d-plane, the answer to our second question is the ways of drawing lines from (0,0) to (n,0). The total routes will be Cnn / 2, but some of them are invalid. Consider another route starting from (0,-2). For each invalid way in the previous route, consider the first point (x,y) that y<0 (y=-1). By creating a symmetry route with y=-1 for the route before this point, this route will become exactly one route starting from (0,-2), and every route starting from (0,-2) will become an invalid route in a similar way. So the number of invalid routes is Cnn / 2 - 1 (that is the number of routes from (0,-2) to (n,0)). Thus the answer will be Cnn / 2 - Cnn / 2 - 1. Similarly if there are [l,r] notes left, the answer will be Cnn / 2 - r / 2 - Cnn / 2 - l / 2 - 1. Now let's enumerate how many customers are there with VIP cards. If there are i of them, the answer will time a factor Cni. One last question is about the modulo number. First separate it into forms like (p1a1) * (p2a2)... where p1... are primes. We can calculate how many factors of p are there in (i!), and the modulo value of the remaining ones. Each time we take out a facter p in (i!), and it becomes some product of numbers that are not divisble by p as well as a remaining part (i / p)!. In this way we can calculate the combination numbers recursively. Finally use CRT to combine them.