F. Большинство
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

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

Все были счастливы программировать, пока внезапно не случился перебой в электроснабжении, и лучший сайт спортивного программирования не вышел из строя. К счастью, системный администратор недавно купил новое оборудование, в том числе несколько ИБП. Таким образом, есть несколько серверов, которые всё ещё находятся в сети, но нам нужно, чтобы они все работали, чтобы раунд остался рейтинговым.

Представьте, что серверы представляют собой бинарную строку $$$s$$$ длины $$$n$$$. Если $$$i$$$-й сервер находится онлайн, то $$$s_i = 1$$$, иначе $$$s_i = 0$$$.

Системный администратор может выполнить следующую операцию под названием распределение электроэнергии, которая состоит из следующих этапов:

  • Выберите два сервера в позициях $$$1 \le i < j \le n$$$ так, чтобы оба были подключены к сети (т. е. $$$s_i=s_j=1$$$). Распределение начинается только с онлайн-серверов.
  • Проверьте, достаточно ли мощности для распространения. Мы считаем, что мощности достаточно, если количество включенных серверов в диапазоне $$$[i, j]$$$ не меньше количества выключенных серверов в диапазоне $$$[i, j]$$$. Более формально, проверьте, что $$$2 \cdot (s_i + s_{i+1} + \ldots + s_j) \ge j - i + 1$$$.
  • Если условие выше выполнено, включите все серверы в оффлайне в диапазоне $$$[i, j]$$$. Более формально, присвоить $$$s_k := 1$$$ для всех $$$k$$$ от $$$i$$$ до $$$j$$$.

Мы называем бинарную строку $$$s$$$ длины $$$n$$$ рейтинговой, если мы можем включить все серверы (т.е. сделать $$$s_i = 1$$$ для $$$1 \le i \le n$$$) с помощью операции распределения электроэнергии произвольное количество раз (возможно, $$$0$$$). Ваша задача — найти количество рейтинговых строк длины $$$n$$$ по модулю $$$m$$$.

Входные данные

Первая и единственная строка содержится два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 5000$$$, $$$10 \le m \le 10^9$$$) — длина строки и требуемый модуль.

Выходные данные

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

Примеры
Входные данные
2 100
Выходные данные
1
Входные данные
3 10
Выходные данные
2
Входные данные
4 3271890
Выходные данные
4
Входные данные
17 123456
Выходные данные
32347
Примечание

В первом примере единственной рейтинговой строкой является 11. Таким образом, ответ $$$1$$$.

Во втором примере рейтинговыми строками являются:

  • 111;
  • 101, потому что мы можем выполнить операцию с $$$i = 1$$$ и $$$j = 3$$$.
Таким образом, ответ равен $$$2$$$.

В третьем примере рейтинговые строки:

  • 1001;
  • 1111;
  • 1011;
  • 1101.
Таким образом, ответ $$$4$$$.