#779. #6044. 「雅礼集训 2017 Day8」共

#6044. 「雅礼集训 2017 Day8」共

题目描述

俗话说,跳蚤国王下江南,火车司机出秦川,共价大爷游长沙。 但是这道题可能跟上面几句话没什么关系。
共价爷想构造一棵 NN 个点的有根树,其中 11 号点是根。
显然的,对于一棵有根树,我们可以定义每个点的深度为,这个点到根的路径上点的个数(包括端点),也就是说,11 号点深度为 11。
共价爷希望,深度为奇数的点的个数,刚好为 KK 个。
他想知道有多少棵不同的满足条件的有根树,你只需要输出答案对 PP 取模的结果。 我们认为两棵树不同,当且仅当存在一对点 (i,j)(i, j),满足 ii 和 jj 在一棵树中有边相连,而在另一棵树中没有边相连。

输入格式

一行三个整数,依次为 NN、KK、PP。

输出格式

一个正整数,表示答案。

4 2 998244353
12

数据范围与提示

对于 5%5\% 的数据,是样例;
对于 20%20\% 的数据,N≤20N \leq 20;
对于 40%40\% 的数据,N≤100N \leq 100;
对于 70%70\% 的数据,N≤1000N \leq 1000,PP 为 10000000071000000007 或 998244353998244353 且均匀分布;
对于 90%90\% 的数据,N≤50000N \leq 50000;
对于 100%100\% 的数据,1<K<N1 \lt K \lt N,N≤500000N \leq 500000,当 N>1000N \gt 1000 时,PP 均为 998244353998244353。