题目描述

年轻的 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 CONTEST 7 T6 KLAVIR，按照原题数据配置，满分 $160$ 分。

由 Eason_AC 翻译整理提供。