Counting Non‐Interval Permutations

Let a permutation of the integers \(1,2,\dots,n\) be called an interval permutation if there exists a contiguous subarray (of length between 2 and \(n-1\)) whose elements, when sorted, form a sequence of consecutive natural numbers. For example, the permutation \(\{6,7,1,8,5,3,2,4\}\) is an interval permutation because subarrays such as \(\{6,7\}\), \(\{5,3,2,4\}\) and \(\{3,2\}\) (after sorting) form a block of consecutive numbers.

A permutation that does not have any such non‐trivial contiguous subarray is called a simple permutation (i.e. it is not an interval permutation). Given two integers \(n\) and \(p\), where \(n\) is the size of the permutation \(\{1,2,\dots,n\}\) and \(p\) is a modulus, your task is to output the number of simple permutations (i.e. permutations that are not interval permutations) modulo \(p\>.

Note: It is known that simple permutations have been studied in permutation patterns. For small values of \(n\) the numbers are as follows:

• \(n=1\): 1
• \(n=2\): 2
• \(n=3\): 0
• \(n=4\): 2
• \(n=5\): 6
• \(n=6\): 46
• \(n=7\): 338
• \(n=8\): 2920
• \(n=9\): 28146
• \(n=10\): 324792

You may assume that \(n\) will be small (\(1 \le n \le 10\)).

inputFormat

The input consists of two space‐separated integers: \(n\) and \(p\).

\(n\) is the size of the permutation \(\{1,2,\dots,n\}\) and \(p\) is the modulus for the output.

outputFormat

Output a single integer: the number of simple (non–interval) permutations of \(\{1,2,\dots,n\}\) modulo \(p\).

sample

1 100

1