#2175. 联赛

内存限制:259 MiB 时间限制:10 Sec

题目描述

问题描述
欧洲杯将至,欧足联在欧洲杯之前宣布了一项决定:成立一个新的联赛——欧洲超级联赛,并将欧洲各豪门俱乐部加入该联赛。
众所周知,各联赛都将转播权卖给各电视台以盈利,欧洲超级联赛自然也不例外,可是问题也随之出现:不同的比赛激烈程度自然不同,例如国际米兰 与尤文图斯 ,曼联 与阿森纳 ,巴萨罗那 与皇家马德里 这样的比赛自然人人都愿意看,可是遇上了利物浦 与切尔西 这样的比赛球迷们就不高兴啦(至少作者会不高兴)
因此欧足联为每场比赛定了一个级别,以此来表示比赛的受欢迎程度。
然而,分级的方法却不只一种。例如,可以将所有比赛分为A,B,C共3种级别,也可以分成W(Wildness,野蛮型),T(Technic,技术型)共2种级别。
可是如果某轮联赛有多种级别的比赛,精明的电视台当然都会购买最激烈的比赛的转播权,这是欧足联的高官们所不愿看到的(因为联赛的盈利会因此减少),所以每轮联赛只能有同一种级别的比赛。
可挑剔的球迷希望:联赛不是循环的(即无法将联赛分为K(K为小于N的任意正整数)段并使这K段都相同),因为这样才不会引起他们的审美疲劳。
已知联赛共有N轮,第i种分级方法有Ri种级别的比赛,现在欧足联想知道在每种分级方法下有多少种安排联赛的方案(注:把某种方案顺移K(K<=N)位后任然是同一种方案,例如,ABC和BCA,CAB为同一种方案,但ABC和ACB不是同一种方案)。为此,欧足联设下了奖品,谁能提供答案谁就能获得这份奖励。

输入格式

 第一行两个数N,M分别表示有N轮联赛和M种分级方法。
 第二行M个数,第i个数为Ri,意义如题

输出格式

 M行,每行一个数ansi表示第i种分级方法下的方案数。


样例

样例输入


			
3 1
3


样例输出


			
8


数据范围与提示

 在样例1中,8种方案分别为AAB,AAC,BBA,BBC,CCA,CCB,ABC,ACB。

数据范围

对于20%的数据,满足M<=10

 对于所有的数据,满足

 N<=1000

M<=100

Ri<=256 (1<=i<=M)