同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21760_ExtremalPermutations

2022-5-16 18:20| 发布者: Hocassian| 查看: 33| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-89505823961399-Problem List-采集的数据-后羿采集器.html

Pro.ID

21760

Title

Extremal Permutations

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21760

AC

Submit

Ratio

时间&空间限制

Time Limit: 40000/20000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

A member a_i of the sequence a₁, a₂, ..., a_n is called a local extreme if either a_i > a_i-1 and a_i > a_i+1 (local maximum) or a_i < a_i-1 and a_i < a_i+1 (local minimum). A sequence p₁, p₂, ..., p_n is called a permutation of the integers from 1 to n if each of the integers appears in the sequence exactly once. A permutation is called extremal if each member (except the first and the last) is a local extreme.

Compute the total number of extremal permutations of the integers from 1 to n and output the result modulo m.

输入

The first and only line of the input file contains the integers n (1 ≤ n ≤ 10000) and m (1 ≤ m ≤ 10⁹)

输出

Description

Compute the total number of extremal permutations of the integers from 1 to n and output the result modulo m.

Input

The first and only line of the input file contains the integers n (1 ≤ n ≤ 10000) and m (1 ≤ m ≤ 10⁹)

Output

The output file should contain a single integer, the remainder from division of the total number of extremal permutations of integers from 1 to n by the given integer m.

Sample Input

Sample #1
3 10

Sample #2
3 3

Sample Output

Sample #1
4

Sample #2
1

Hint

The extremal permutations of 1...3 are (1, 3, 2), (2, 1, 3), (2, 3, 1) and (3, 1, 2).

Source

NEERC 2009 Western Subregional