P9799 [NERC 2018] Interval-Free Permutations

Translated from Problem I of [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf).

We define a permutation of $1 \sim n$ to be an “interval permutation” if there exists a contiguous subarray of length $2 \sim n - 1$ such that, after sorting, the elements in this subarray form a sequence of consecutive natural numbers. For example, $\{6,7,1,8,5,3,2,4\}$ is an “interval permutation”, because $\{6,7\}$, $\{5,3,2,4\}$, and $\{3,2\}$ all become a consecutive sequence of natural numbers after sorting. Given $n$, output the number of permutations that are **not** “interval permutations”. Since the answer may be very large, output it modulo $p$.

The first line contains two integers $t (1 \leq t \leq 400)$ and $p (10^8 \leq p \leq 10^9)$, representing the number of test cases and the modulus. The next $t$ lines each contain one integer $n (1 \leq n \leq 400)$.

For each test case, output the number of permutations of $1 \sim n$ that are **not** “interval permutations”, modulo $p$.

The constraints guarantee $1 \leq t \leq 400$, $10^8 \leq p \leq 10^9$, and $1 \leq n \leq 400$. Explanation for Sample 1: For the second test case, $\{2,4,1,3\}$ and $\{3,1,4,2\}$ satisfy the requirement. For the third test case, $\{2,4,1,5,3\}$, $\{2,5,3,1,4\}$, $\{3,1,5,2,4\}$, $\{3,5,1,4,2\}$, $\{4,1,3,5,2\}$, and $\{4,2,5,1,3\}$ satisfy the requirement. For Sample 2, there are $264111424634864638$ possibilities in total. Translated by ChatGPT 5