[ARC096E] Everything on It

对于集合 $\{1,2,\dots,n\}$，求它的子集族中，有多少个满足： 1. 任意两个子集互不相同； 1. $1,2,\dots,n$ 都在其中至少出现了 $2$ 次。 答案对 $M$ 取模。 $2\le n\le 3000,10^8\le M\le10^9+9,M\in \text{prime}$

[problemUrl]: https://atcoder.jp/contests/arc096/tasks/arc096_c ラーメン店「高橋屋」のメニューは基本的には「ラーメン」の一つだけですが、$ N $ 種類のトッピングも提供されています。客がラーメンを注文するとき、それぞれの種類のトッピングを「乗せる」か「乗せない」かを選ぶことができます。乗せるトッピングの数に制限はなく、すべてのトッピングを乗せることも、トッピングを一つも乗せないこともできます。つまり、トッピングの組み合わせを考慮すると $ 2^N $ 通りのラーメンを注文できます。 赤木さんが高橋屋に入店しました。彼女は、次の二つの条件をともに満たすようにラーメンを何杯か注文しようと考えています。 - トッピングの組み合わせがまったく同じラーメンを複数杯注文しない。 - $ N $ 種類のトッピングそれぞれが、注文したラーメンのうち $ 2 $ 杯以上に乗っている。 $ N $ と素数 $ M $ が与えられます。これらの条件を満たすようなラーメンの組み合わせの数を $ M $ で割ったあまりを求めてください。ラーメンの順番は考慮しません。また、赤木さんは極限の空腹状態にあるため、ラーメンを何杯注文しても問題ありません。

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

条件を満たすようなラーメンの組み合わせの数を $ M $ で割ったあまりを出力せよ。

2 1000000007

2

3 1000000009

118

50 111111113

1456748

3000 123456791

16369789

### 制約 - $ 2\ \leq\ N\ \leq\ 3000 $ - $ 10^8\ \leq\ M\ \leq\ 10^9\ +\ 9 $ - $ N $ は整数である。 - $ M $ は素数である。 ### 部分点 - $ N\ <\ =\ 50 $ を満たすテストセットに正解すると、$ 600 $ 点が与えられる。 ### Sample Explanation 1 $ 2 $ 種類のトッピングを A, B とします。注文できるラーメンは「トッピングなし」「A 乗せ」「B 乗せ」「A, B 乗せ」の $ 4 $ 通りです。条件を満たすラーメンの組み合わせは次の $ 2 $ 通りです。 - 「A 乗せ」「B 乗せ」「A, B 乗せ」の $ 3 $ 杯 - 全通りのラーメン $ 1 $ 杯ずつ、合計 $ 4 $ 杯 ### Sample Explanation 2 $ 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 がどのラーメンにも乗っていないためです。 ### Sample Explanation 3 組み合わせの数を $ M $ で割ったあまりを出力することをお忘れなく。なお、以上の三つの入力例は、部分点のためのテストセットに含まれます。 ### Sample Explanation 4 この入力例は、部分点のためのテストセットに含まれません。