Interval-Free Permutations

Consider a permutation p₁, p₂, …, p_n of integers from 1 to n. We call a sub-segment p_l, p_l+1, …, p_r−1, pr 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 ≤ t ≤ 400) and p (10⁸ ≤ p ≤ 10⁹) — the number of test cases to solve and the prime modulo. In each of the next t lines there is one integer n (1 ≤ n ≤ 400) — the length of the permutation.

详情