年轻的 Alisa 喜欢只用一根手指弹钢琴。不幸的是，Alisa 从未学过弹钢琴，所以她的弹奏完全是随机的。更具体地说，每次她选择一个音符弹奏时，都是独立于之前所有音符的，并且以相同的概率选择 $N$ 个音符中的每一个。

她的好朋友 Mirta 想要听一段包含 $M$ 个连续音符的乐曲，但由于 Alisa 是随机弹奏钢琴的，Mirta 不知道自己需要等待多久才能听到恰好是这 $M$ 个音符的序列。请帮助 Mirta 确定为了首次听到她想要的连续音符序列，期望的按键次数。此外，由于 Mirta 是一个非常好奇的女孩，她还想知道听到她想要的音符序列的每个前缀所需的期望按键次数。

输入格式

第一行包含一个正整数 $N$，表示不同钢琴音符的数量（$1 \le N \le 100$）。

第二行包含一个正整数 $M$，表示目标序列的长度（$1 \le M \le 10^6$）。

第三行包含由 $M$ 个介于 $1$ 和 $N$ 之间的正整数组成的序列。

输出格式

接下来的 $M$ 行中，第 $i$ 行必须包含 Mirta 听到她目标音符序列长度为 $i$ 的前缀所需的期望按键次数，模 $10^9 + 7$ 的结果。

测试数据保证期望的按键次数总是整数。

子任务

在价值 64 分的测试用例中，满足 $1 \le M \le 200$。

样例

输入样例 1

2
2
1 2

输出样例 1

2
4

输入样例 2

2
2
1 1

输出样例 2

2
6

输入样例 3

3
3
1 2 3

输出样例 3

3
9
27