Ай и Лань, живущие в маленькой вселенной номер 998244353, получили послание от «Возвращающих к нулю» и решили откликнуться на движение возвращения. Им необходимо вернуть большую часть материи в Большую Вселенную, оставив лишь ничтожно малую часть для восстановления своей цивилизации в новой вселенной.

Цивилизация Ай и Лань обладает в общей сложности $n$ ключевыми фрагментами информации, пронумерованными от $1, 2, \dots, n$. Информация, которую им необходимо сохранить, представляет собой подмножество $S$ этих ключевых фрагментов. Для фрагмента с номером $x$, если сумма номеров некоторого подмножества элементов из $S$ равна $x$, то разработанная ими «бутылка с посланием» сможет восстановить $x$ в новой вселенной.

Ай и Лань задумались: сколько существует способов выбрать подмножество $S$ так, чтобы все ключевые фрагменты информации $1, 2, \dots, n$ могли быть восстановлены? Ай и Лань, разумеется, вычислили точное количество способов всего за 1 микросекунду, а теперь они хотят, чтобы вы помогли им проверить результат. Поскольку количество способов может быть очень большим, вам нужно вывести результат по модулю $M$.

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

В единственной строке записаны два целых положительных числа $N$ и $M$.

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

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

Примеры

Пример 1

4 1000000007

3

Примечание

Существует 3 подмножества, удовлетворяющих условию: $\{1, 2, 3\}$ $\{1, 2, 4\}$ * $\{1, 2, 3, 4\}$

Пример 2

10 1000000007

180

Пример 3

1000 65472

2136

Пример 4

100000 100

96

Ограничения

Для 100% данных гарантируется, что $1 \le N \le 5 \times 10^5$, $2 \le M \le 1.01 \times 10^9$.