D. Нефрен и кинотеатр
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лахеш любит снимать фильмы, поэтому Нефлен помогает ей организовать кинотеатр, который называется кинотеатр 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 различных очередей.