[COCI2016-2017#7] KLAVIR

年轻的 Alisa 喜欢只用一根手指弹钢琴。但是，由于 Alisa 从来都没学过弹钢琴，因此她的弹琴过程完全是随机的。更准确地说，她会**等概率**选择钢琴的 $N$ 个音调上的任意一个，并且**独立于之前所有选择的音调**。 Alisa 的好朋友 Mirta 想要听一个连续的包含 $M$ 个音调 $A_1,A_2,\dots,A_M$ 的曲子，但由于 Alisa 弹琴过程是完全随机的，Mirta 只想知道，对于所有的 $1\leqslant i\leqslant M$，Alisa 选择音调使 Mirta 第一次听到连续的音调 $A_1,A_2,\dots,A_i$ 的**期望次数**。为了防止精度丢失，**答案对 $\bf 10^9+7$ 取模**。

第一行输入一个整数 $N$，表示音调个数。 第二行输入一个整数 $M$，表示 Mirta 想要听的曲子包含的音调个数。 随后 $M$ 行，每行一个整数 $A_i$，表示曲子的第 $i$ 个音调。

输出 $M$ 行，每行一个正整数，第 $i$ 行表示 Alisa 选择音调使 Mirta 第一次听到连续的音调 $A_1,A_2,\dots,A_i$ 的期望次数对 $\bf 10^9+7$ 取模之后的结果。

2
2
1 2

2
4

2
2
1 1

2
6

3
3
1 2 3

3
9
27

**【数据范围】** 对于 $40\%$ 的数据，保证 $1\leqslant M\leqslant 200$。 对于所有数据，$1\leqslant N\leqslant 100$，$1\leqslant M\leqslant 10^6$，$1\leqslant A_i\leqslant N$。 **【题目来源】** 本题来源自 **_[COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST 7](https://hsin.hr/coci/archive/2016_2017/contest7_tasks.pdf) T6 KLAVIR_**，按照原题数据配置，满分 $160$ 分。 由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。