TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3798
  • 题目
  • P3798有趣的数列
    限制 : 时间限制 : - MS   空间限制 : 65536 KB
    评测说明 : 1000ms
    问题描述

     

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

       (1)它是从1到2n共2n个整数的一个排列{Ai};

       (2)所有的奇数项满足A1<A3<…<A2n-1,所有的偶数项满足A2<A4<…<A2n;

       (3)任意相邻的两项A2i-1与A2i(1≤i≤n)满足奇数项小于偶数项,即:A2i-1<A2i。

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

    输入格式

    用空格隔开的两个整数n和P。

    50%的数据满足n≤1000

    100%的数据满足n≤1000000且P≤1000000000。

    输出格式

    仅含一个整数,表示不同的长度为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)。


    来源  hnoi2009