Alternating Mountain Permutations

Long ago, legends told of mysterious creatures called gnomes that inhabited the mountains. A mountain range is represented as a sequence of n contiguous segments with unique heights which are a permutation of the numbers \(1,2,\dots,n\). For a segment with height \(h_i\):

• If the segment is higher than all of its adjacent segments, it is called a peak.
• If it is lower than all its adjacent segments, it is called a valley.

Note that an edge segment has only one neighbor. The gnomes have a custom that every segment in the mountain must be buildable either as a look-out tower (only on a peak) or as a tavern (only in a valley). In other words, each segment must be either a peak or a valley for the mountain to be suitable for gnome habitation.

This means that for every segment \(1 \leq i \leq n\), if it has two neighbors (i.e. when \(2 \le i \le n-1\)), the following condition must hold: \[ \Bigl(h_{i} - h_{i-1}\Bigr)\cdot\Bigl(h_{i} - h_{i+1}\Bigr) > 0. \] For the edge segments the condition is automatic since they have only one adjacent segment.

Your task is: Given an integer n and a modulus p, count the number of mountain ranges (i.e. permutations of \(\{1,2,\dots,n\}\)) such that every segment is a peak or a valley. Two mountain ranges are considered different if they differ in at least one segment. Output the answer modulo p.

Note: Since the number of valid mountain ranges may be huge, we only require the remainder modulo p.

inputFormat

The input consists of a single line containing two integers n and p (\(1 \le n \le 10\), \(p \ge 1\)).

Note: Here, n is small (\(n \le 10\)) so that a brute force solution examining all \(n!\) permutations will pass.

outputFormat

Output a single integer: the number of valid mountain ranges modulo p.

sample

1 100

1