/ 
Time Limit: 4 sec / Memory Limit: 512 MB
配点 : 900 点
問題文
ラーメン店「高橋屋」のメニューは基本的には「ラーメン」の一つだけですが、N 種類のトッピングも提供されています。客がラーメンを注文するとき、それぞれの種類のトッピングを「乗せる」か「乗せない」かを選ぶことができます。乗せるトッピングの数に制限はなく、すべてのトッピングを乗せることも、トッピングを一つも乗せないこともできます。つまり、トッピングの組み合わせを考慮すると 2^N 通りのラーメンを注文できます。
赤木さんが高橋屋に入店しました。彼女は、次の二つの条件をともに満たすようにラーメンを何杯か注文しようと考えています。
- トッピングの組み合わせがまったく同じラーメンを複数杯注文しない。
- N 種類のトッピングそれぞれが、注文したラーメンのうち 2 杯以上に乗っている。
N と素数 M が与えられます。これらの条件を満たすようなラーメンの組み合わせの数を M で割ったあまりを求めてください。ラーメンの順番は考慮しません。また、赤木さんは極限の空腹状態にあるため、ラーメンを何杯注文しても問題ありません。
制約
- 2 \leq N \leq 3000
- 10^8 \leq M \leq 10^9 + 9
- N は整数である。
- M は素数である。
部分点
- N ≤ 50 を満たすテストセットに正解すると、600 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
条件を満たすようなラーメンの組み合わせの数を M で割ったあまりを出力せよ。
入力例 1
2 1000000007
出力例 1
2
2 種類のトッピングを A, B とします。注文できるラーメンは「トッピングなし」「A 乗せ」「B 乗せ」「A, B 乗せ」の 4 通りです。条件を満たすラーメンの組み合わせは次の 2 通りです。
- 「A 乗せ」「B 乗せ」「A, B 乗せ」の 3 杯
- 全通りのラーメン 1 杯ずつ、合計 4 杯
入力例 2
3 1000000009
出力例 2
118
3 種類のトッピングを A, B, C とします。入出力例 1 で述べた 4 通りのラーメンに加えて、それらに C を付け足した 4 通りのラーメンも注文できます。条件を満たすラーメンの組み合わせは 118 通りありますが、そのうちのいくつかを挙げます。
- 「A, B 乗せ」「A, C 乗せ」「B, C 乗せ」の 3 杯
- 「トッピングなし」「A 乗せ」「A, B 乗せ」「B, C 乗せ」「A, B, C 乗せ」の 5 杯
- 全通りのラーメン 1 杯ずつ、合計 8 杯
なお、「『A 乗せ』『B 乗せ』『A, B 乗せ』の 3 杯」は条件を満たしません。C がどのラーメンにも乗っていないためです。
入力例 3
50 111111113
出力例 3
1456748
組み合わせの数を M で割ったあまりを出力することをお忘れなく。なお、以上の三つの入力例は、部分点のためのテストセットに含まれます。
入力例 4
3000 123456791
出力例 4
16369789
この入力例は、部分点のためのテストセットに含まれません。
Score : 900 points
Problem Statement
In "Takahashi-ya", a ramen restaurant, basically they have one menu: "ramen", but N kinds of toppings are also offered. When a customer orders a bowl of ramen, for each kind of topping, he/she can choose whether to put it on top of his/her ramen or not. There is no limit on the number of toppings, and it is allowed to have all kinds of toppings or no topping at all. That is, considering the combination of the toppings, 2^N types of ramen can be ordered.
Akaki entered Takahashi-ya. She is thinking of ordering some bowls of ramen that satisfy both of the following two conditions:
- Do not order multiple bowls of ramen with the exactly same set of toppings.
- Each of the N kinds of toppings is on two or more bowls of ramen ordered.
You are given N and a prime number M. Find the number of the sets of bowls of ramen that satisfy these conditions, disregarding order, modulo M. Since she is in extreme hunger, ordering any number of bowls of ramen is fine.
Constraints
- 2 \leq N \leq 3000
- 10^8 \leq M \leq 10^9 + 9
- N is an integer.
- M is a prime number.
Subscores
- 600 points will be awarded for passing the test set satisfying N ≤ 50.
Input
Input is given from Standard Input in the following format:
N M
Output
Print the number of the sets of bowls of ramen that satisfy the conditions, disregarding order, modulo M.
Sample Input 1
2 1000000007
Sample Output 1
2
Let the two kinds of toppings be A and B. Four types of ramen can be ordered: "no toppings", "with A", "with B" and "with A, B". There are two sets of ramen that satisfy the conditions:
- The following three ramen: "with A", "with B", "with A, B".
- Four ramen, one for each type.
Sample Input 2
3 1000000009
Sample Output 2
118
Let the three kinds of toppings be A, B and C. In addition to the four types of ramen above, four more types of ramen can be ordered, where C is added to the above four. There are 118 sets of ramen that satisfy the conditions, and here are some of them:
- The following three ramen: "with A, B", "with A, C", "with B, C".
- The following five ramen: "no toppings", "with A", "with A, B", "with B, C", "with A, B, C".
- Eight ramen, one for each type.
Note that the set of the following three does not satisfy the condition: "'with A', 'with B', 'with A, B'", because C is not on any of them.
Sample Input 3
50 111111113
Sample Output 3
1456748
Remember to print the number of the sets modulo M. Note that these three sample inputs above are included in the test set for the partial score.
Sample Input 4
3000 123456791
Sample Output 4
16369789
This sample input is not included in the test set for the partial score.