Expected Distance in Random Tree via Prüfer Subsequence

Given an integer n and a sequence a of m positive integers (each in [1, n]), we randomly choose a subsequence of length n-2 (indices chosen must be distinct; the order is preserved) to form a Prüfer sequence. It is well known that a labeled tree on n vertices is uniquely determined by its Prüfer sequence. For each vertex i (1 ≤ i < n), compute the expected value of the distance from vertex i to vertex n in the tree T constructed in this way. The distance dist(u, v) is defined as the number of edges in the simple path between u and v.

Output the answer modulo \(10^9+7\). All formulas must be written in LaTeX, for example, the distance is defined as \(\mathrm{dist}(u,v)\) and the modulus operation is taken modulo \(10^9+7\).

Note: If you are not familiar with the Prüfer sequence, please consult standard texts on Cayley’s formula and tree encoding.

inputFormat

The first line contains two integers n and m.

The second line contains m integers \(a_1, a_2, \dots, a_m\) where \(1 \le a_i \le n\).

outputFormat

Output n-1 integers separated by spaces. The i-th integer represents the expected value of \(\mathrm{dist}(i, n)\) modulo \(10^9+7\).

sample

3 3
1 2 3

1 1