Background

Translated from Problem I of NERC 2018.

Problem Description

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$.

Input Format

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)$.

Output Format

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

4 998244353
1
4
5
9

1
2
6
28146

1 437122297
20

67777575

Hint

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