题目描述

ラーメン店「高橋屋」のメニューは基本的には「ラーメン」の一つだけですが、$N$ 種類のトッピングも提供されています。客がラーメンを注文するとき、それぞれの種類のトッピングを「乗せる」か「乗せない」かを選ぶことができます。乗せるトッピングの数に制限はなく、すべてのトッピングを乗せることも、トッピングを一つも乗せないこともできます。つまり、トッピングの組み合わせを考慮すると $2^N$ 通りのラーメンを注文できます。

赤木さんが高橋屋に入店しました。彼女は、次の二つの条件をともに満たすようにラーメンを何杯か注文しようと考えています。

• トッピングの組み合わせがまったく同じラーメンを複数杯注文しない。
• $N$ 種類のトッピングそれぞれが、注文したラーメンのうち $2$ 杯以上に乗っている。

$N$ と素数 $M$ が与えられます。これらの条件を満たすようなラーメンの組み合わせの数を $M$ で割ったあまりを求めてください。ラーメンの順番は考慮しません。また、赤木さんは極限の空腹状態にあるため、ラーメンを何杯注文しても問題ありません。

输入格式

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

$N$ $M$

输出格式

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

题目大意

对于集合 $\{1,2,\dots,n\}$，求它的子集族中，有多少个满足：

1. 任意两个子集互不相同；
2. $1,2,\dots,n$ 都在其中至少出现了 $2$ 次。

答案对 $M$ 取模。

$2\le n\le 3000,10^8\le M\le10^9+9,M\in \text{prime}$

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

この入力例は、部分点のためのテストセットに含まれません。