#PQJ2818x16220. QOJ 2818_16220

    ID: 2874 传统题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:HNOI 2009组合数学

QOJ 2818_16220

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

它是从 1 到 2 𝑛 共 2 𝑛 个整数的一个排列 𝑎 𝑖 ; 所有的奇数项满足 𝑎 1 < 𝑎 3 < ⋯ < 𝑎 2 𝑛 − 1 ,所有的偶数项满足 𝑎 2 < 𝑎 4 < ⋯ < 𝑎 2 𝑛 ; 任意相邻的两项 𝑎 2 𝑖 − 1 与 𝑎 2 𝑖 ( 1 ≤ 𝑖 ≤ 𝑛 )满足奇数项小于偶数项,即: 𝑎 2 𝑖 − 1 < 𝑎 2 𝑖 。

现在的任务是:对于给定的 𝑛 ,求出有多少个不同的长度为 2 𝑛 的有趣的数列。因为最后的答案可能很大,所以只要求输出答案 mod   𝑃 的值。

输入格式

输入文件只包含用空格隔开的两个整数 𝑛 和 𝑃 。输入数据保证: 50% 的数据满足 𝑛 ≤ 1000 ,100% 的数据满足 𝑛 ≤ 1000000 且 𝑃 ≤ 1000000000 。

输出格式

输出仅包含一个整数,表示不同的长度为 2 𝑛 的有趣的数列个数 mod   𝑃 的值。

样例数据 input.txt 3 10 output.txt 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 ) 。