489. Extremal Permutations
Time limit per test: 0.5
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
A member
a_{i} of the sequence
a_{1},
a_{2}, ·s,
a_{n} is called a
if either
a_{i} >
a_{i1} and
a_{i} >
a_{i+1} (local maximum) or
a_{i} <
a_{i1} and
a_{i} <
a_{i+1} (local minimum). A sequence
p_{1},
p_{2}, ·s,
p_{n} is called a
of the integers from 1 to
n if each of the integers appears in the sequence exactly once. A permutation is called
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.
Input
The first and only line of the input file contains the integers
n (
) and
m (1 ≤
m ≤ 10
^{9}).
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.
Example(s)
sample input

sample output

3 10

4

sample input

sample output

3 3

1

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