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