配点 : $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 \leq 50$ を満たすテストセットに正解すると、$600$ 点が与えられる。

入力

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

$N$ $M$

出力

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

2 1000000007

2

$2$ 種類のトッピングを A, B とします。注文できるラーメンは「トッピングなし」「A 乗せ」「B 乗せ」「A, B 乗せ」の $4$ 通りです。条件を満たすラーメンの組み合わせは次の $2$ 通りです。

• 「A 乗せ」「B 乗せ」「A, B 乗せ」の $3$ 杯
• 全通りのラーメン $1$ 杯ずつ、合計 $4$ 杯

3 1000000009

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 がどのラーメンにも乗っていないためです。

50 111111113

1456748

組み合わせの数を $M$ で割ったあまりを出力することをお忘れなく。なお、以上の三つの入力例は、部分点のためのテストセットに含まれます。

3000 123456791

16369789

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