Mieszkańcy małego wszechświata o numerze 998244353, Ai i Lan, otrzymali wiadomość od "Powracających do zera" i postanowili odpowiedzieć na ruch powrotny. Muszą zwrócić większość materii do wielkiego wszechświata, pozostawiając jedynie znikomą jej ilość, aby odbudować swoją cywilizację w nowym wszechświecie.
Cywilizacja Ai i Lan posiada łącznie $n$ kluczowych informacji, ponumerowanych od $1, 2, \dots, n$. Informacje, które muszą zachować, stanowią podzbiór $S$ tych kluczowych informacji. Dla informacji o numerze $x$, jeśli suma numerów pewnego podzbioru zbioru $S$ jest równa $x$, to zaprojektowana przez nich butelka z wiadomością pozwoli na odtworzenie $x$ w nowym wszechświecie.
Ai i Lan zastanawiają się, na ile sposobów mogą wybrać podzbiór $S$, aby każdą z kluczowych informacji $1, 2, \dots, n$ można było odtworzyć. Ai i Lan naturalnie obliczyli dokładną liczbę sposobów w zaledwie 1 mikrosekundę, a teraz chcą, abyś pomógł im to zweryfikować. Ponieważ liczba sposobów może być bardzo duża, wystarczy, że wyprowadzisz wynik modulo $M$.
Wejście
Wiersz zawiera dwie dodatnie liczby całkowite $N, M$.
Wyjście
Wyprowadź jedną liczbę całkowitą, oznaczającą wynik modulo $M$.
Podzadania
Dla 100% danych wejściowych zachodzi $1 \le N \le 5 \times 10^5$ oraz $2 \le M \le 1.01 \times 10^9$.
| Numer testu | $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$ |
Przykład
Wejście 1
4 1000000007
Wyjście 1
3
Uwagi
Istnieją łącznie 3 zbiory spełniające warunek: $\{1, 2, 3\}$ $\{1, 2, 4\}$ * $\{1, 2, 3, 4\}$
Wejście 2
10 1000000007
Wyjście 2
180
Wejście 3
1000 65472
Wyjście 3
2136
Wejście 4
100000 100
Wyjście 4
96