For a multiset $S$ with size at most $n$, where each element is an integer in $[0, n]$, we define an operation $\text{SaM}$ (Select and Mex) as follows:
- Choose any non-empty sub-multiset $T$.
- Calculate $x = \text{mex} \, T$.
- Remove $T$ from $S$ and add $x$ to $S$.
For a given $S$, let $f(S)$ denote the maximum number of distinct elements in $S$ after performing any number of $\text{SaM}$ operations.
SA-chan gives you a subset $T$ of $S$. You need to find the number of multisets $S$ of size $n$ that satisfy the following conditions:
- $T \subseteq S$
- $0 \in S$
- $f(S) = k$
You only need to output the answer modulo $10^9+7$.
Input
The first line contains two integers $n$ and $|T|$.
If $|T| \ne 0$, the second line contains $|T|$ integers representing the elements in $T$.
Output
For each $k = 1, 2, \dots, n$, output the corresponding answer.
Examples
Input 1
3 0
Output 1
0 3 7
Input 2
6 2 2 2
Output 2
0 0 0 50 30 4
Input 3
12 4 2 5 5 6
Output 3
0 0 0 0 0 470 5530 17352 22065 4655 308 8
Note
When $S = \{0, 1, 1\}, \{0, 0, 1\}, \{0, 0, 0\}$, we have $f(S) = 2$; for all other $S$, $f(S) = 3$.
Constraints
For all test cases, $2 \le n \le 200$, $0 \le |T| \le n$, and elements of $T \in [0, n] \cap \mathbb{Z}$.
| Subtask | Score | Special Properties | ||
|---|---|---|---|---|
| 1 | 15 | $ | T | = n$ |
| 2 | 15 | $n \le 12$ | ||
| 3 | 15 | $n \le 30$ | ||
| 4 | 20 | $n \le 70$ | ||
| 5 | 15 | $n \le 120$ | ||
| 6 | 20 | $n \le 200$ |