998244353番小宇宙に住む艾（アイ）と蘭（ラン）は、帰零者からのメッセージを受け取り、回帰運動に応じることにした。彼らは物質の大部分を大宇宙に返還し、新宇宙で自分たちの文明を再建するためにごくわずかな物質だけを残す必要がある。
艾と蘭の文明には合計 $n$ 個の重要な情報があり、それぞれ $1, 2, \dots, n$ と番号が付けられている。彼らが保持すべき情報は、これらの重要な情報の部分集合 $S$ である。番号 $x$ の情報について、$S$ のある部分集合の番号の和が $x$ に等しければ、彼らが設計した漂流瓶によって新宇宙で $x$ を復元することができる。
艾と蘭は、重要な情報 $1, 2, \dots, n$ のすべてが復元可能となるような部分集合 $S$ の選び方が何通りあるか考えた。艾と蘭はわずか1マイクロ秒でその正確な値を計算したが、今、彼らはあなたに検算を頼みたいと考えている。答えは非常に大きくなる可能性があるため、答えを $M$ で割った余りを出力せよ。
入力
一行に2つの正整数 $N, M$ が与えられる。
出力
答えを $M$ で割った余りを一行に出力せよ。
入出力例
入力 1
4 1000000007
出力 1
3
注記 1
以下の3つの集合が条件を満たす。
- $\{1, 2, 3\}$
- $\{1, 2, 4\}$
- $\{1, 2, 3, 4\}$
入力 2
10 1000000007
出力 2
180
入力 3
1000 65472
出力 3
2136
入力 4
100000 100
出力 4
96
小課題
すべてのデータにおいて、$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$ |