题目背景

Ysuperman 模板测试的计数题。

众所周知，Prüfer 序列几乎没有在正赛中出现过，所以它需要出现在洛谷月赛中。

题目描述

众所周知，一棵 $n$ 个点的有标号无根树与他的 Prüfer 序列一一对应。如果你不知道 Prüfer 序列指的是什么，可以参考下面提示说明中对 Prüfer 序列的解释。

现在给你一个长度为 $m$ 的正整数序列 $a$，其中 $a_i\in[1,n]$。等概率随机选择这个序列的一个长度为 $n-2$ 的子序列（只要选择下标不同就认为两个子序列不同）作为 Prüfer 序列构造得到一棵树 $T$，对于所有 $1\le i<n$，你需要求出 $\mathrm{dist}(i,n)$ 的期望（$\mathrm{dist}(u,v)$ 定义为 $u,v$ 两点简单路径的边数）。

答案对 $10^9+7$ 取模。

输入格式

输入第一行两个正整数 $n,m$。

第二行 $m$ 个整数表示序列 $a$，保证 $1\le a_i\le n$。

输出格式

输出 $n-1$ 个非负整数，第 $i$ 个整数表示 $\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

提示

对 Prüfer 序列的解释

对于一棵给定的无根有标号树，Prüfer 序列的构建过程如下：每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点，重复 $n-2$ 次后就只剩下两个结点，此时记录下来的那个序列就是这棵无根有标号树的 Prüfer 序列。

我们可以证明，一棵结点数量大于 $1$ 的无根有标号树和一个 Prüfer 序列是一一对应的，并且任意一个长度为 $n-2$ 每个数取 $[1,n]$ 范围内的整数的 Prüfer 序列都有唯一对应它的树，所以同样的，我们也可以根据一个 Prüfer 序列还原出一棵树。

有关 Prüfer 序列更加详细的内容，你可以参考 OI wiki 上关于 Prüfer 序列的描述。

样例 1 解释

共有三种等可能选择的子序列：$2,4$，$2,3$，$4,3$。

1. $2,4$ 对应的树为一条链 $1-2-4-3$，其中 $1,2,3$ 与 $4$ 的距离分别为 $2,1,1$。
2. $2,3$ 对应的树为一条链 $1-2-3-4$，其中 $1,2,3$ 与 $4$ 的距离分别为 $3,2,1$。
3. $4,3$ 对应的树为一条链 $1-4-3-2$，其中 $1,2,3$ 与 $4$ 的距离分别为 $1,2,1$。

所以 $\mathrm{dist}(1,4)$ 期望为 $(2+3+1)/3=2$，$\mathrm{dist}(2,4)$ 期望为 $(1+2+2)/3=5/3\equiv 666666673\pmod{10^9+7}$，$\mathrm{dist}(3,4)$ 期望为 $(1+1+1)/3=1$。

样例 2 解释

仅有一种可能的子序列 $4,6,5,2$，对应的树为一条链 $1-4-5-2-6-3$，$1,2,3,4,5$ 与 $6$ 的距离依次为 $4,1,1,3,2$，即为答案。

数据范围

本题共 $20$ 个测试点：

测试点编号	$n$	$m$
$1$	$=4$	$=6$
$2$	$=8$	$=15$
$3$	$=10$	$=20$
$4$		$=50$
$5$		$=200$
$6$		$=1000$
$7$		$=1750$
$8$		$=2500$
$9$	$=11$	$=500$
$10$		$=1000$
$11$	$=12$	$=250$
$12$		$=375$
$13$		$=400$
$14$	$=13$	$=80$
$15$		$=120$
$16$		$=160$
$17$		$=200$
$18$	$=14$	$=60$
$19$		$=90$
$20$	$=15$	$=40$

另外，对于所有数据，保证 $1\le a_i\le n$。

请注意，前 $19$ 个测试点空间限制为 $512\rm{MB}$，最后一个点空间限制为 $150\rm{MB}$。