29595번 - MP3-плеер 다국어

Вася недавно купил себе новый MP3-плеер doPi Shuffle. Этот плеер отличается от всех других, которые использовал Вася, тем, что у него есть функция <<перемешивания>> списка проигрываемых песен (плейлиста).

Вася загрузил в плеер $n$ своих любимых песен. До этого он их постоянно слушал на компьютере и очень хорошо запомнил порядок, в котором они были в плейлисте.

Разумеется, плеер переставил песни в случайном порядке. Прослушав плейлист несколько раз на плеере, Вася с удивлением обнаружил, что никакие две, шедшие подряд друг за другом в старом плейлисте, не идут подряд в новом. Он задумался, насколько часто возможна такая ситуация.

Пронумеруем песни числами от 1 до $n$ в том порядке, в котором они идут в плейлисте на компьютере. Напишите программу, которая вычисляет число способов их переставить так, чтобы никакие две песни с последовательными номерами не шли непосредственно друг за другом. Так как это число может быть достаточно большим, выведите его по модулю $m$.

Входной файл содержит два целых числа: $n$ и $m$ ($2 \le n \le 2000$, $2 \le m \le 10^9$).

В выходной файл выведите остаток от деления числа способов переставить песни требуемым образом на $m$.