【提示】
本来であればタイトルにふさわしい背景ストーリーがあるはずでしたが、作者が怠慢であったため、競技開始までに一文字も書かれませんでした。将来、Lightnovel OJ で皆さんとお会いできることを期待しています。
$k$-順列とは、すべての $1 \le i < n$ に対して $|p_i - p_{i+1}| \neq k$ を満たす順列 $p$ のことを指します。
正整数 $n$ と $M$ が与えられます。続いて $q$ 回のクエリが与えられ、各クエリで $k$ が指定されます。$n$ 次順列のうち、$k$-順列であるものがいくつあるかを答えてください。答えは非常に大きくなる可能性があるため、$M$ で割った余りを出力してください。
入力
入力は以下の形式で与えられる。
$n \ q \ M$ $k_1$ $k_2$ $\vdots$ $k_q$
出力
$q$ 行出力せよ。各行に、$k$-順列の個数を $M$ で割った余りを出力すること。
入出力例
入出力例 1
5 5 998244353 1 2 3 4 5
14 28 48 72 120
入出力例 2
入出力例 3
小課題
すべてのデータにおいて、$1 \le k \le n \le 2,000$、$10^8 \le M \le 10^9$ を満たし、入力される $k$ はすべて異なる。 また、99% のデータにおいて $n \le 10^3$ を満たす。
| 小課題 | 配点 | $n$ | $k$ | $q$ | $M$ は素数 |
|---|---|---|---|---|---|
| 1 | 10 | $\le 9$ | $\le 9$ | $= n$ | Yes |
| 2 | 14 | $\le 16$ | - | - | - |
| 3 | 15 | $\le 200$ | $= 1$ | $= 1$ | - |
| 4 | 16 | - | - | $= n$ | - |
| 5 | 8 | $\le 10^3$ | $= 1$ | $= 1$ | - |
| 6 | 9 | - | $= 2$ | - | - |
| 7 | 16 | - | - | - | - |
| 8 | 11 | - | - | $= n$ | No |
| 9 | 1 | $\le 2,000$ | - | - | - |