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

Memory Limit:512 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

但是这道题可能跟上面几句话没什么关系。
共价爷想构造一棵 N N N 个点的有根树,其中 1 1 1 号点是根。
显然的,对于一棵有根树,我们可以定义每个点的深度为,这个点到根的路径上点的个数(包括端点),也就是说,1 1 1 号点深度为 1 1 1
共价爷希望,深度为奇数的点的个数,刚好为 K K K 个。
他想知道有多少棵不同的满足条件的有根树,你只需要输出答案对 P P P 取模的结果。

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

输入格式

一行三个整数,依次为 N N NK K KP P P

输出格式

一个正整数,表示答案。

样例

样例输入

4 2 998244353

样例输出

12

数据范围与提示

对于 5% 5\% 5% 的数据,是样例;
对于 20% 20\% 20% 的数据,N≤20 N \leq 20 N20
对于 40% 40\% 40% 的数据,N≤100 N \leq 100 N100
对于 70% 70\% 70% 的数据,N≤1000 N \leq 1000 N1000P P P1000000007 1000000007 1000000007998244353 998244353 998244353 且均匀分布;
对于 90% 90\% 90% 的数据,N≤50000 N \leq 50000 N50000
对于 100% 100\% 100% 的数据,1<K<N 1 < K < N 1<K<NN≤500000 N \leq 500000 N500000,当 N>1000 N > 1000 N>1000 时,P P P 均为 998244353 998244353 998244353