题目描述

俗话说，跳蚤国王下江南，火车司机出秦川，共价大爷游长沙。

但是这道题可能跟上面几句话没什么关系。 共价爷想构造一棵 $N$ 个点的有根树，其中 $1$ 号点是根。

显然的，对于一棵有根树，我们可以定义每个点的深度为，这个点到根的路径上点的个数（包括端点），也就是说，$1$ 号点深度为 $1$。

共价爷希望，深度为奇数的点的个数，刚好为 $K$ 个。

他想知道有多少棵不同的满足条件的有根树，你只需要输出答案对 $P$ 取模的结果。

我们认为两棵树不同，当且仅当存在一对点 $(i, j)$，满足 $i$ 和 $j$ 在一棵树中有边相连，而在另一棵树中没有边相连。

输入格式

一行三个整数，依次为 $N$、$K$、$P$。

输出格式

一个正整数，表示答案。

4 2 998244353

12

提示

对于 $5\%$ 的数据，是样例；

对于 $20\%$ 的数据，$N \leq 20$；

对于 $40\%$ 的数据，$N \leq 100$；

对于 $70\%$ 的数据，$N \leq 1000$，$P$ 为 $1000000007$ 或 $998244353$ 且均匀分布；

对于 $90\%$ 的数据，$N \leq 50000$；

对于 $100\%$ 的数据，$1 < K < N$，$N \leq 500000$，当 $N > 1000$ 时，$P$ 均为 $998244353$。