#P1485. [HNOI2009]有趣的数列

    ID: 497 传统题 1000ms 512MiB 尝试: 2451 已通过: 908 难度: 6 上传者: 标签>CF1900提高双射计数Catalan 数反射原理线性筛质因数指数约分快速幂

[HNOI2009]有趣的数列

[HNOI2009] 有趣的数列

题目描述

我们称一个长度为 2n2n 的数列是有趣的,当且仅当该数列满足以下三个条件:

  • 它是从 1∼2n1 \sim 2n 共 2n2n 个整数的一个排列 {an}n=12n\{a_n\}_{n=1}^{2n};

  • 所有的奇数项满足 a1<a3<⋯<a2n−1a_1<a_3< \dots < a_{2n-1},所有的偶数项满足 a2<a4<⋯<a2na_2<a_4< \dots <a_{2n};

  • 任意相邻的两项 a2i−1a_{2i-1} 与 a2ia_{2i} 满足:a2i−1<a2ia_{2i-1}<a_{2i}。

对于给定的 nn,请求出有多少个不同的长度为 2n2n 的有趣的数列。
因为最后的答案可能很大,所以只要求输出答案对 pp 取模。

输入格式

一行两个正整数 n,pn,p

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

3 10

样例输出 #1

5

提示

【数据范围】
对于 50%50\% 的数据,1≤n≤10001\le n \le 1000;
对于 100%100\% 的数据,1≤n≤1061\le n \le 10^6,1≤p≤1091\le p \le 10^9。

【样例解释】
对应的5个有趣的数列分别为 $(1,2,3,4,5,6), (1,2,3,5,4,6), (1,3,2,4,5,6), (1,3,2,5,4,6), (1,4,2,5,3,6)$。