Задача №1706. Пилообразная перестановка
Необходимо подсчитать по модулю числа M количество перестановок чисел от 1 до N, являющихся пилообразными. Напомним, что пилообразной называется последовательность чисел, в которой для всех чисел (кроме первого и последнего) выполнено условие: \(a_{i - 1} < a_i > a_{i + 1}\) или \(a_{i - 1} > a_i < a_{i + 1}\).
Формат входных данных
Входной файл содержит два числа \(N\) и \(M (1 ≤ N ≤ 10 000, 1 ≤ M ≤ 10^9)\).
Формат выходных данных
Выведите единственное число — ответ на задачу.
Примечание
Пилообразными перестановками трех чисел являются (1, 3, 2), (2, 1, 3), (2, 3, 1) и (3, 1, 2).
Примеры
Входные данные
3 10
Выходные данные
4
Входные данные
3 3
Выходные данные
1
Сдать: для сдачи задач необходимо войти в систему