/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 800 点
問題文
正整数 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 で割った余りを求めてください．
制約
- 1\leq N\leq 700
- P は 10^8\lt P\lt 10^9 を満たす素数
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる．
N P
出力
答えを出力せよ．
入力例 1
1 998244353
出力例 1
2
得られる A は (0),(1) の 2 通りです．
入力例 2
2 998244353
出力例 2
7
得られる A は (0,0),(0,2),(1,0),(1,2),(1,3),(3,2),(3,3) の 7 通りです．
入力例 3
3 998244353
出力例 3
57
入力例 4
4 998244353
出力例 4
1208
入力例 5
77 777777773
出力例 5
381787647
Score : 800 points
Problem Statement
You are given a positive integer N and a prime P.
There is a length-N sequence A=(A_1,A_2,\ldots,A_N) where all elements are 0.
You can repeat the following operation any number of times, possibly zero:
- Choose a non-empty subset S of \lbrace 1,2,\ldots,N\rbrace. Let \displaystyle x=\sum_{i\in S}2^{i-1}. For each i\in S, replace A_i with x.
Find the number, modulo P, of possible sequences A after repeating the operations.
Constraints
- 1\leq N\leq 700
- P is a prime satisfying 10^8\lt P\lt 10^9.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P
Output
Output the answer.
Sample Input 1
1 998244353
Sample Output 1
2
The possible sequences A are (0),(1), giving two possibilities.
Sample Input 2
2 998244353
Sample Output 2
7
The possible sequences A are (0,0),(0,2),(1,0),(1,2),(1,3),(3,2),(3,3), giving seven possibilities.
Sample Input 3
3 998244353
Sample Output 3
57
Sample Input 4
4 998244353
Sample Output 4
1208
Sample Input 5
77 777777773
Sample Output 5
381787647