问题 Z: 有趣的数列

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:2 通过:2

题目描述

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

  1. 它是从 1 到 2n 共 2n 个整数的一个排列 {ai}
  2. 所有的奇数项满足 a1<a3<<a2n1,所有的偶数项满足 a2<a4<<a2n
  3. 任意相邻的两项a2i1 与 a2i(1in) 满足奇数项小于偶数项,即:a2i1<a2i

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

输入格式

只包含用空格隔开的两个整数 n 和 P
对于 50% 的数据,n1000,P106
对于全部数据,1n106,2P109

输出格式

仅含一个整数,表示不同的长度为 2n 的有趣的数列个数  modP 的值。

输入样例 复制

3 10

输出样例 复制

5