Background

Ysuperman's template testing problem on counting.

As is well known, Prüfer sequences have rarely appeared in formal competitions, so they need to appear in Luogu Monthly Contests.

Problem Description

It is well known that a labeled, rooted tree with $n$ nodes corresponds uniquely to its Prüfer sequence. If you are unfamiliar with what a Prüfer sequence is, refer to the explanation of Prüfer sequences in the Notes/Hints section below.

You are given a sequence $a$ of length $m$ where each $a_i$ is a positive integer in the range $[1, n]$. A subsequence of length $n-2$ is chosen uniformly at random from this sequence (subsequences are considered different if they select different indices) to construct a tree $T$ using the Prüfer sequence. For all $1 \leq i < n$, you need to find the expected value of $\mathrm{dist}(i, n)$ ($\mathrm{dist}(u, v)$ is defined as the number of edges on the simple path between nodes $u$ and $v$).

The answer should be modulo $10^9 + 7$.

Input Format

The first line of input contains two positive integers $n$ and $m$.

The second line contains $m$ integers representing the sequence $a$, with $1 \leq a_i \leq n$.

Output Format

Output $n-1$ non-negative integers, where the $i$-th integer represents the expected value of $\mathrm{dist}(i, n)$.

Sample Input and Output

Sample Input #1

4 3
2 4 3

Sample Output #1

2 666666673 1

Sample Input #2

6 4
4 6 5 2

Sample Output #2

4 1 1 3 2

Sample Input #3

10 12
6 9 2 10 1 5 5 9 10 7 8 3

Sample Output #3

585858594 60606064 8080810 834343444 638383846 785858595 913131322 595959602 286868692

Notes/Hints

Explanation of Prüfer Sequence

For a given labeled, rooted tree, the construction of its Prüfer sequence is as follows: repeatedly select the leaf node with the smallest label, remove it, and record the node it was connected to. Repeat this process $n-2$ times until only two nodes remain. The sequence recorded is the Prüfer sequence of the tree.

It can be proven that a labeled, rooted tree with more than one node corresponds uniquely to a Prüfer sequence, and any Prüfer sequence of length $n-2$ with numbers in the range $[1, n]$ corresponds uniquely to a tree. Therefore, we can also reconstruct a tree from a given Prüfer sequence.

For more detailed information about Prüfer sequences, refer to the description on OI wiki.

Sample 1 Explanation

There are three equally likely subsequences to choose from: $2,4$, $2,3$, and $4,3$.

1. The tree corresponding to $2,4$ is a chain $1-2-4-3$, with distances from $1,2,3$ to $4$ being $2,1,1$ respectively.
2. The tree corresponding to $2,3$ is a chain $1-2-3-4$, with distances from $1,2,3$ to $4$ being $3,2,1$ respectively.
3. The tree corresponding to $4,3$ is a chain $1-4-3-2$, with distances from $1,2,3$ to $4$ being $1,2,1$ respectively.

Thus, the expected value of $\mathrm{dist}(1,4)$ is $(2+3+1)/3 = 2$, $\mathrm{dist}(2,4)$ is $(1+2+2)/3 = 5/3 \equiv 666666673 \pmod{10^9+7}$, and $\mathrm{dist}(3,4)$ is $(1+1+1)/3 = 1$.

Sample 2 Explanation

There is only one possible subsequence $4,6,5,2$, corresponding to a chain $1-4-5-2-6-3$, with distances from $1,2,3,4,5$ to $6$ being $4,1,1,3,2$ respectively, which is the answer.

Data Range

There are a total of 20 test cases:

Additionally, for all data, it is guaranteed that $1 \leq a_i \leq n$.

Note that the first 19 test cases have a space limit of 512 MB, and the last test case has a space limit of 150 MB.

见题面 Input 部分

见题面 Output 部分