| Codeforces Round 449 (Div. 1) |
|---|
| Закончено |
Лахеш любит снимать фильмы, поэтому Нефлен помогает ей организовать кинотеатр, который называется кинотеатр 68.
Однажды в кинотеатре 68 кончились деньги (у них нет купюр достоинством в 50 юаней в данный момент), но Нефлен всё равно хочет открыть его.
В кассу кинотеатра приходят три типа покупателей: одни приносят ровно одну купюру достоинством в 50 юаней, вторые приносят ровно одну купюру достоинством в 100 юаней, поэтому Нефлен должна дать им сдачу одной купюрой в 50 юаней, а третьи приходят с VIP картой, поэтому не должны платить за билет.
Сейчас n посетителей стоят снаружи кинотеатра в очереди. Нефлен хочет узнать, сколько возможных очередей могут быть таких, чтобы все люди смогли купить билет (то есть каждый покупатель мог получить сдачу, если она требуется), и чтобы после продажи билетов всем покупателям в кассе осталось не менее l и не более r купюр достоинством 50 юаней. Две очереди называются различными, если существует позиция, на которой в этих очередях стоят покупатели разного типа. Так как ответ может быть большим, выведите его по модулю p.
В первой строке содержатся четыре целых числа n (1 ≤ n ≤ 105), p (1 ≤ p ≤ 2·109), l and r (0 ≤ l ≤ r ≤ n).
Выведите единственное число — ответ на задачу по модулю p.
4 97 2 3
13
4 100 0 4
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 различных очередей.
