2399 问题 K: 信息学奥赛一本通T1661-有趣的数列

时间限制: 1s 内存限制: 128MB 提交: 19 解决: 5
题目描述
我们称一个长度为 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。

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


                
                
                

                                        

                        
                        

                                                            
                                
                                                        
                            
                            
                            
                        

                    

                

                


                

            

            

                

                    

                        
比赛公告

                    

                    

                        

                            
三次元银河系太阳系地球中国江苏省泰州市海陵区万达广场1号楼4单元301电脑房里的刘梓枫。
                        

                    

                

                

                    

                        
比赛状况