AT_arc096_c [ARC096E] Everything on It

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

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 3000 $ - $ 10^8\ \leq\ M\ \leq\ 10^9\ +\ 9 $ - $ N $ は整数である。 - $ M $ は素数である。 ### 部分点 - $ N\