题意

我们称一个长度为2n的数列是有趣的，当且仅当该数列满足以下三个条件：$我们称一个长度为2n的数列是有趣的，当且仅当该数列满足以下三个条件：$ (1)它是从1到2n共2n个整数的一个排列ai；$(1)它是从1到2n共2n个整数的一个排列{ai}；$ (2)所有的奇数项满足a1<a3<…<a2n−1，所有的偶数项满足a2<a4<…<a2n；$(2)所有的奇数项满足a1 <nobr>(3)任意相邻的两项a2i−1与a2i(1≤i≤n)满足奇数项小于偶数项，即：a2i−1&lt;a2i。</nobr><script type="math/tex" id="MathJax-Element-71"> (3)任意相邻的两项a2i-1与a2i(1≤i≤n)满足奇数项小于偶数项，即：a2i-1 <nobr>现在的任务是：对于给定的n，请求出有多少个不同的长度为2n的有趣的数列。因为最后的答案可能很大，所以只要求输出答案modP的值。</nobr><script type="math/tex" id="MathJax-Element-72"> 现在的任务是：对于给定的n，请求出有多少个不同的长度为2n的有趣的数列。因为最后的答案可能很大，所以只要求输出答案 mod P的值。$ n≤1000000，P≤1000000000。$n≤1000000，P≤1000000000。$

分析

这么菜的题我都没有想到。。。一头撞死算了。 考虑每次都找最前的奇数位或最前的偶数位来放数字，但有第三个限制所以任意时刻偶数位不能多于奇数位，于是问题就变成了卡特兰数。 直接线性筛分解质因数即可。

代码