题目描述

年轻的 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$ 取模之后的结果。

样例 #1

样例输入 #1

2
2
1 2

样例输出 #1

2
4

样例 #2

样例输入 #2

2
2
1 1

样例输出 #2

2
6

样例 #3

样例输入 #3

3
3
1 2 3

样例输出 #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$