간격 없는 순열

$1$부터 $n$까지의 정수로 이루어진 순열 $p_1, p_2, \ldots, p_n$을 생각하자. 순열의 연속된 부분 $p_l, p_{l+1}, \ldots, p_r$이 연속된 정수 집합을 재배열한 것이면 이를 구간이라고 한다. 예를 들어 순열 $(6, 7, 1, 8, 5, 3, 2, 4)$에는 $(6, 7)$, $(5, 3, 2, 4)$, $(3, 2)$ 등의 구간이 있다.

모든 순열에는 자명한 구간이 있다. 순열 전체와 원소 하나로 이루어진 구간이 그것이다. 길이가 $2$ 이상 $n-1$ 이하인 자명하지 않은 구간이 없는 순열을 간격 없는 순열이라고 한다.

길이가 $n$인 간격 없는 순열의 개수를 소수 $p$로 나눈 나머지를 구하라.

첫 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 400$)와 소수 $p$ ($10^8 \le p \le 10^9$)가 주어진다. 이후 $t$개의 줄에는 순열의 길이 $n$ ($1 \le n \le 400$)이 한 줄에 하나씩 주어진다.

각 테스트 케이스마다 길이가 $n$인 간격 없는 순열의 개수를 $p$로 나눈 나머지를 한 줄에 출력한다.

$n = 1$이면 유일한 순열이 간격 없는 순열이다. $n = 4$이면 간격 없는 순열은 $(2, 4, 1, 3)$과 $(3, 1, 4, 2)$ 두 개이다. $n = 5$이면 $(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)$, $(4, 2, 5, 1, 3)$ 여섯 개이다. $n = 9$이면 28146개이므로 전부 나열하지 않는다. 예를 들어 $(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)$, $(8, 4, 9, 1, 3, 6, 2, 7, 5)$는 간격 없는 순열이다.