AT_arc221_b [ARC221B] Two-Powered Sum

正整数 $ N $ と素数 $ P $ が与えられます． すべての要素が $ 0 $ である長さ $ N $ の数列 $ A=(A_1,A_2,\ldots,A_N) $ があります． あなたは以下の操作を $ 0 $ 回以上好きな回数繰り返すことができます． - 非空な $ \lbrace 1,2,\ldots,N\rbrace $ の部分集合 $ S $ を選ぶ． $ \displaystyle x=\sum_{i\in S}2^{i-1} $ として，各 $ i\in S $ に対して $ A_i $ を $ x $ で置き換える． 操作を繰り返すことで最終的に得られる $ A $ としてあり得るものの個数を $ P $ で割った余りを求めてください．

入力は以下の形式で標準入力から与えられる． > $ N $ $ P $

答えを出力せよ．

### Sample Explanation 1 得られる $ A $ は $ (0),(1) $ の $ 2 $ 通りです． ### Sample Explanation 2 得られる $ A $ は $ (0,0),(0,2),(1,0),(1,2),(1,3),(3,2),(3,3) $ の $ 7 $ 通りです． ### Constraints - $ 1\leq N\leq 700 $ - $ P $ は $ 10^8\lt P\lt 10^9 $ を満たす素数 - 入力される数値は全て整数