Interval-Free Permutations

题意翻译

给您一个模数 $p$ 和 $n$，请您输出长度为 $n$ 同时不包含连续子段的排列方案总数。 translated by @kyron✅

题目描述

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

输入输出样例

输入样例 #1

4 998244353
1
4
5
9

输出样例 #1

1
2
6
28146

输入样例 #2

1 437122297
20

输出样例 #2

67777575

说明

For $ n = 1 $ the only permutation is interval-free. For $ n = 4 $ two interval-free permutations are $ (2,4,1,3) $ and $ (3,1,4,2) $ . For $ 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) $ , and $ (4,2,5,1,3) $ . We will not list all 28146 for $ n = 9 $ , but for example $ (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) $ are interval-free. The exact value for $ n = 20 $ is 264111424634864638.