Республиканская олимпиада по информатике, 2012 год, 9 класс

(Казарма)

Ограничение по времени:

2 секунды

Ограничение по памяти:

64 мегабайта

В казарме $N$ рядовых солдат. Когда в казарму входит старший сержант, они строятся в ряд. После построения старший сержант идет от первого солдата к последнему и по своему желанию выбирает троих. Эти солдаты делают шаг вперед. Если они стоят в порядке возрастания роста, то у командира хорошее настроение, и он отпускает всех. Если он никак не может выбрать трех солдат так, чтобы у него было хорошее настроение, он злится и заставляет всех бегать весь день.
    Известно, что у всех солдат рост разный. Один любопытный солдат хочет знать, сколькими способами все солдаты могут встать в строй так, чтобы старший сержант был доволен. Так как ответ может быть большим, выведите его по модулю $M.$

Формат входного файла

В единственной строке входного файла задаются два целых числа $N$ и $M,$ разделенных пробелом $(3 \le N \le 25000,$ $1 \le M \le 2 \cdot 10^9).$

Формат выходного файла

Выведите ответ к задаче.

Примеры:

Вход

3 10000

Ответ

1

Вход

5 10000

Ответ

78

Замечание

В не менее $20\%$ тестов $N \le 10.$ В не менее $50\%$ тестов $N \le 500.$ В не менее $75\%$ тестов $N \le 4000.$