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

<img class="tex-graphics" src="https://espresso.codeforces.com/61558e055f8ced114442e7bb5661924edc0d402a.png" style="max-width: 100.0%;max-height: 100.0%;"/>

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*.
One line containing four integers *n* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>), *p* (1 ≤ *p* ≤ 2·10<sup class="upper-index">9</sup>), *l* and *r* (0 ≤ *l* ≤ *r* ≤ *n*).
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.
4 97 2 3
13
4 100 0 4
35
13 143 6 11
129
999 998244353 666 777
974283165
23333 1000000007 0 23333
192355111
100000 100160063 2332 99774
68169009
100000 996991027 54321 67890
884435812
1 1 0 0
0
1 1 0 1
0
1 233332 0 0
1
1 999888663 0 1
2
1 2000000000 1 1
1
2 14 0 0
2
2 39 0 1
4
2 1999999999 0 2
5
2 15 1 1
2
2 2 1 2
1
2 3 2 2
1
3 6 0 0
4
3 9 0 1
0
3 12 0 2
0
3 999 0 3
13
3 998244352 1 1
5
3 5241 1 2
8
3 18 1 3
9
3 2 2 2
1
3 1234567890 2 3
4
3 16 3 3
1
4 17 2 4
14
4 1 1 3
0
4 12 0 3
10
4 4 2 3
1
4 7 0 0
2
4 14 4 4
1
95 10007 23 77
181
95 1001 16 88
381
1024 1073741824 16 512
716646144
2287 1895283097 97 2084
1319976811
6536 692001792 2018 6535
81144575
23333 764411904 222 23333
405536868
23333 764411904 0 23332
164956607
57684 1987654320 1 57683
1266501185
65536 1987654320 33333 44444
1184495760
89701 223092870 235 87777
167375370
93527 223092870 0 93527
60956070
98760 1338557220 16384 65536
1287074250
99998 1561650090 10387 99771
1402030596
99999 1293938646 55447 55447
639859770
99999 2000000000 66666 66666
1847813839
100000 901800900 8765 98765
207662400
100000 1073741824 2 98304
754182784
100000 1064246657 7147 83628
605219868
100000 491986259 0 100000
188914619
100000 1 98766 99877
0
100000 1285743549 0 0
975152502
100000 1784742960 125 99988
1592494880
def mult(m1, m2):
    p = len(m1)
    q = len(m2)
    r = len(m2[0])
    m3 = [[0] * r for _ in range(p)]
    for x in range(p):
        for y in range(r):
            for z in range(q):
                m3[x][y] += m1[x][z] * m2[z][y]
                m3[x][y] %= pio
    return m3


def binpow(mat, x):
    if x == 0:
        return E
    elif x % 2:
        return mult(mat, binpow(mult(mat, mat), x // 2))
    else:
        return binpow(mult(mat, mat), x // 2)


n, pio, l, r = map(int, input().split())
matrix = [[0] * (n+1) for _ in range(n+1)]
E = [[0]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    E[i][i] = 1
for i in range(n+1):
    for j in range(n+1):
        if abs(i - j) <= 1:
            matrix[i][j] = 1
start = [[1]]
for _ in range(n):
    start.append([0])
matrix = binpow(matrix, n)
start = mult(matrix, start)
ans = 0
for p in range(l, r + 1):
    ans += start[p][0]
print(ans)