Ай и Лань, живущие в маленькой вселенной номер 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$.
| Номер теста | $N \le$ | $M \le$ |
|---|---|---|
| 1, 2 | 20 | $1.01 \times 10^9$ |
| 3, 4 | $10^2$ | $1.01 \times 10^9$ |
| 5, 6 | 5,000 | $1.01 \times 10^9$ |
| 7 | $3 \times 10^5$ | 127 |
| 8 | $5 \times 10^5$ | 127 |
| 9 | $3 \times 10^5$ | $1.01 \times 10^9$ |
| 10 | $5 \times 10^5$ | $1.01 \times 10^9$ |