Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

2018-2019 ICPC, NEERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

I. Interval-Free Permutations

time limit per test

1.5 secondsmemory limit per test

512 megabytesinput

standard inputoutput

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

Input

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.

Output

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

Examples

Input

4 998244353 1 4 5 9

Output

1 2 6 28146

Input

1 437122297 20

Output

67777575

Note

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.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/22/2020 10:38:34 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|