Consider a permutation $p_1, p_2, \dots p_n$ of integers from 1 to $n$. We call a sub-segment $p_l, p_{l+1}, \dots, p_{r-1}, p_{r}$ of the permutation 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.

Each permutation has some trivial intervals — the full permutation itself and every single element. We call a permutation interval-free if it does not have non-trivial intervals. In other words, interval-free permutation does not have intervals of length between 2 and $n - 1$ inclusive.

Your task is to count the number of interval-free permutations of length $n$ modulo prime number $p$.

In the first line of the input there are two integers $t$ ($1 \le t \le 400$) and $p$ ($10^8 \le p \le 10^9$) — the number of test cases to solve and the prime modulo. In each of the next $t$ lines there is one integer $n$ ($1 \le n \le 400$) — the length of the permutation.

For each of $t$ test cases print a single integer — the number of interval-free permutations modulo $p$.