Interval-Free Permutations

Consider a permutation $p_1, p_2, \ldots, p_n$ of the integers from $1$ to $n$. A sub-segment $p_l, p_{l+1}, \ldots, p_r$ is called an interval if it is a reordering of some set of consecutive integers. For example, the permutation $(6, 7, 1, 8, 5, 3, 2, 4)$ has the intervals $(6, 7)$, $(5, 3, 2, 4)$, $(3, 2)$, and others.

Every permutation has trivial intervals: the full permutation and every single element. A permutation is interval-free if it has no non-trivial intervals, meaning no intervals of length between $2$ and $n-1$ inclusive.

Count the interval-free permutations of length $n$ and print the result modulo the prime $p$.

The first line contains two integers $t$ ($1 \le t \le 400$) and $p$ ($10^8 \le p \le 10^9$), the number of test cases and the prime modulo. Each of the next $t$ lines contains one integer $n$ ($1 \le n \le 400$), the length of the permutation.

For each test case, print a single integer: the number of interval-free permutations of length $n$ modulo $p$.

For $n = 1$, the only permutation is interval-free. For $n = 4$, the interval-free permutations are $(2, 4, 1, 3)$ and $(3, 1, 4, 2)$. For $n = 5$, they are $(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)$. For $n = 9$ there are $28146$ of them, so the full list is omitted. Examples include $(4, 7, 9, 5, 1, 8, 2, 6, 3)$, $(2, 4, 6, 1, 9, 7, 3, 8, 5)$, $(3, 6, 9, 4, 1, 5, 8, 2, 7)$, and $(8, 4, 9, 1, 3, 6, 2, 7, 5)$.