题目描述

$(1,2,\ldots,N)$ の順列を、以下では単に順列と呼びます。

二つの順列 $A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N)$ にたいして、類似度 を以下の条件を満たす $1$ 以上 $N-1$ 以下の整数 $i$ の個数で定めます。

• $(A_{i+1}-A_i)(B_{i+1}-B_i)\ >\ 0$

二つの順列の組 $(A,B)$ であって、類似度が $K$ であるものの個数を素数 $P$ で割ったあまりを答えてください。

输入格式

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

$N$ $K$ $P$

输出格式

答えを出力せよ。

题目大意

长为 $N$ 的排列 $A$ 与 $B$ 的相似度被定义为：

• 满足 $(A_{i+1}-A_i)(B_{i+1}-B_i)>0$，其中 $1\le i<N$ 的 $i$ 的数量。

求有多少对 $1\sim N$ 的排列相似度恰为 $K$，对 $P$ 取模。

3 1 282282277

16

50 25 998244353

131276976

提示

制約

• $2\leq\ N\ \leq\ 100$
• $0\leq\ K\ \leq\ N-1$
• $10^8\ \leq\ P\ \leq\ 10^9$
• $P$ は素数
• 入力は全て整数である

Sample Explanation 1

例えば条件を満たす順列の組の一つとして、以下のものが考えられます。 - $A=(1,2,3)$ - $B=(1,3,2)$ この例では、$(A_2\ -\ A_1)(B_2\ -B_1)\ >\ 0,\ (A_3\ -\ A_2)(B_3\ -B_2)\ <\ 0$ であることから、$A$ と $B$ の類似度は $1$ だとわかります。

Sample Explanation 2

個数を $P$ で割ったあまりを答えてください。