题目描述
我们称一个长度为 2n 的数列是有趣的,当且仅当该数列满足以下三个条件:
- 它是从 1 到 2n 共 2n 个整数的一个排列 {ai};
- 所有的奇数项满足 a1<a3<⋯<a2n−1,所有的偶数项满足 a2<a4<⋯<a2n;
- 任意相邻的两项 a2i−1 与 a2i (1≤i≤n) 满足奇数项小于偶数项,即:a2i−1<a2i。
任务是:对于给定的 n,请求出有多少个不同的长度为 2n 的有趣的数列。因为最后的答案可能很大,所以只要求输出答案 mod P 的值。
输入格式
只包含用空格隔开的两个整数 n 和 P。
输出格式
仅含一个整数,表示不同的长度为 2n 的有趣的数列个数 mod P 的值。
3 10
5
对应的 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\}$。
提示
对于 50% 的数据,n≤1000,P≤106;
对于全部数据,1≤n≤106,2≤P≤109。