题目描述

年轻的 Alisa 喜欢只用一个手指弹钢琴。不幸的是，Alisa 从未学习过弹钢琴。所以她的弹奏时完全随机的。更准确地说，每次她都会从 $n$ 个音符中等概率随机弹奏一个音符。

她的好朋友 Mirta 想要听一首包含 $m$ 个连续音符的曲子，由于 Alisa 随机弹钢琴，Mirta 不知道她要等多久才能听到她希望听到的曲子。Mirta 是一个好奇的女孩，她想知道这首曲子的每一个前缀的期望弹奏次数。

输入格式

第一行包含两个正整数 $n,m$。

第二行包含 $m$ 个整数 $a_i$，表示 Mirta 想听到的曲子。

输出格式

输出 $m$ 行，每行一个整数，表示前缀 $1\sim i$ 出现时，期望弹奏的次数 $\bmod 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\le m \le 200$。

对于 $100\%$ 的数据，$1\le n \le 100$，$1\le m\le10^6$，$1\le a_i \le n$。

题目来源

题目译自 COCI2016-2017 Contest#7 T6 Klavir。