Busy Beaver бросил программирование и решил заняться современным искусством!

У Busy Beaver есть два жетона с краской. Он хочет раскрасить неориентированный граф следующим образом:

• Изначально все вершины не раскрашены. Сначала Busy Beaver помещает один жетон на вершину 1, а другой — на вершину 2.
• Затем он перемещает жетоны вдоль ребер графа; когда вершина оказывается под жетоном, она становится раскрашенной. (Заметьте, что вершины 1 и 2 изначально считаются раскрашенными.)
• Если можно раскрасить все вершины так, чтобы два жетона никогда не находились в вершинах, соединенных ребром, в любой момент процесса, то такой граф называется художественным.

Найдите количество художественных неориентированных графов с $N$ вершинами. Поскольку ответ может быть большим, выведите его по модулю простого числа $P$.

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

Единственная строка каждого теста содержит два целых числа $N$ и $P$ ($2 \le N \le 5000$; $5 \cdot 10^8 < P < 10^9$). $P$ — простое число.

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

Выведите количество художественных неориентированных графов с $N$ вершинами по модулю $P$.

Примеры

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

2 799999999

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

1

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

3 998244853

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

2

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

1984 998244853

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

424428556

Примечание

В первом тестовом примере граф с двумя вершинами и без ребер является единственным художественным графом.

Во втором тестовом примере первые два графа ниже являются художественными. Последний граф не является художественным, так как невозможно раскрасить вершину 3.

Иллюстрация к примеру 2