E. Феникс и компьютеры
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В один ряд стоят $$$n$$$ компьютеров, первоначально все выключены, и Феникс хочет всех их включить. Он будет лично включать их по одному. Однако в любой момент времени, если компьютеры $$$i-1$$$ и $$$i+1$$$ оказались включены, то компьютер $$$i$$$ $$$(2 \le i \le n-1)$$$ включится сам автоматически (если он еще не включен). Заметим, что Феникс не может включить компьютер, который уже включился автоматически.

Рассмотрим только последовательности компьютеров, включенных непосредственно Фениксом, сколько существует таких последовательностей, включающих все компьютеры? Две последовательности различны, если либо множество компьютеров, включенных лично Фениксом, различается, либо порядок их включения различен. Так как ответ может быть слишком большим, выведите его по модулю $$$M$$$.

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

В первой строке заданы два целых числа $$$n$$$ и $$$M$$$ ($$$3 \le n \le 400$$$; $$$10^8 \le M \le 10^9$$$) — количество компьютеров и модуль. Гарантируется, что $$$M$$$ — простое.

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

Выведите одно число — количество способов включить все компьютеры по модулю $$$M$$$.

Примеры
Входные данные
3 100000007
Выходные данные
6
Входные данные
4 100000007
Выходные данные
20
Входные данные
400 234567899
Выходные данные
20914007
Примечание

В первом примере, для Феникса есть $$$6$$$ последовательностей, при которых он включит все компьютеры:

  • $$$[1,3]$$$. Включить компьютер $$$1$$$, потом $$$3$$$. Заметим, что компьютер $$$2$$$ включится автоматически после того, как компьютер $$$3$$$ будет включен Фениксом, но мы учитываем только компьютеры, включенные непосредственно Фениксом.
  • $$$[3,1]$$$. Включить компьютер $$$3$$$, потом $$$1$$$.
  • $$$[1,2,3]$$$. Включить компьютеры $$$1$$$, потом $$$2$$$, затем $$$3$$$.
  • $$$[2,1,3]$$$
  • $$$[2,3,1]$$$
  • $$$[3,2,1]$$$