Background

A counting problem for Ysuperman’s template testing.

As everyone knows, the Prüfer sequence has almost never appeared in official contests, so it needs to appear in a Luogu Monthly Contest.

Problem Description

As everyone knows, a labeled unrooted tree with $n$ nodes corresponds one-to-one with its Prüfer sequence. If you do not know what a Prüfer sequence is, you can refer to the explanation in the Hint section below.

Now you are given a positive integer sequence $a$ of length $m$, where $a_i\in[1,n]$. Uniformly at random, choose a subsequence of this sequence with length $n-2$ (as long as the chosen indices are different, the two subsequences are considered different) and use it as a Prüfer sequence to construct a tree $T$. For all $1\le i<n$, you need to compute the expected value of $\mathrm{dist}(i,n)$ (where $\mathrm{dist}(u,v)$ is defined as the number of edges on the simple path between nodes $u$ and $v$).

Output the answer modulo $10^9+7$.

Input Format

The first line contains two positive integers $n,m$.

The second line contains $m$ integers representing the sequence $a$, and it is guaranteed that $1\le a_i\le n$.

Output Format

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

4 3
2 4 3

2 666666673 1

6 4
4 6 5 2

4 1 1 3 2

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

585858594 60606064 8080810 834343444 638383846 785858595 913131322 595959602 286868692

Hint

Explanation of the Prüfer sequence

For a given unrooted labeled tree, the construction process of its Prüfer sequence is as follows: each time, select the leaf node with the smallest label and delete it, then record in the sequence the node it is connected to. Repeat this $n-2$ times; after that, only two nodes remain, and the recorded sequence is the Prüfer sequence of this unrooted labeled tree.

We can prove that an unrooted labeled tree with more than $1$ node corresponds one-to-one with a Prüfer sequence, and that any Prüfer sequence of length $n-2$ with each number being an integer in $[1,n]$ has a unique corresponding tree. Similarly, we can also restore a tree from a Prüfer sequence.

For more detailed content about the Prüfer sequence, you can refer to the description of the Prüfer sequence on OI-wiki.

Sample 1 explanation

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

1. The tree corresponding to $2,4$ is a chain $1-2-4-3$, and the distances from $1,2,3$ to $4$ are $2,1,1$, respectively.
2. The tree corresponding to $2,3$ is a chain $1-2-3-4$, and the distances from $1,2,3$ to $4$ are $3,2,1$, respectively.
3. The tree corresponding to $4,3$ is a chain $1-4-3-2$, and the distances from $1,2,3$ to $4$ are $1,2,1$, respectively.

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

Sample 2 explanation

There is only one possible subsequence $4,6,5,2$, and the corresponding tree is a chain $1-4-5-2-6-3$. The distances from $1,2,3,4,5$ to $6$ are $4,1,1,3,2$ in order, which is the answer.

Constraints

This problem has a total of $20$ test points:

In addition, for all testdata, it is guaranteed that $1\le a_i\le n$.

Please note that the memory limit for the first $19$ test points is $512\rm{MB}$, and the memory limit for the last test point is $150\rm{MB}$.

Translated by ChatGPT 5