Start: Oct, 05, 2021 12:00:00
模拟赛二
End: Oct, 23, 2021 16:00:00
Time elapsed:
Time remaining:

伤害值 1191

Time Limit:  1 Sec    Memory Limit:   256 MB
Submission:36     AC:6     Score:100


Description

大家都知道gsy最近一直都在玩游戏,现在gsy使用的是一个伤害非常高的角色。

这个角色在打怪时会给怪物叠加一种名为 `怒意狂击` 的 debuff,能够有效增加他的伤害,这个 debuff 会让怪物每次受到的伤害增加 x

而这个英雄最可怕的地方在于,这个 debuff 是可以叠加的,而且叠加效果呈几何形式增长!

也就是当叠加了两次 `怒意狂击` 以后,怪物每次受到的额外伤害将会是 x^2,当叠加了三次 `怒意狂击` 以后,怪物每次受到的额外伤害将会是 x^3!

现在gsy一顿操作以后只记得他对每种怪物在每次 debuff 状态下攻击了多少次,请你告诉他他总共造成了多少点伤害

Input

第一行包含两个整数 x,n。x 含义如题,n 表示gsy总共给怪物叠加了 n 次 debuff$

接下来 n + 1 行,第 i 行一个整数 ai 含义如下

a0 表示除了 debuff 伤害以外gsy总共造成了多少伤害

a1 表示在 1 层 debuff 状态下攻击了 a1 次
...
an 表示在 n 层 debuff 状态下攻击了 an 次

对于 100% 的数据,1 <= n <= 100000, x <= 10, 0 <= ai <= 100

Output

输出结果的最后 100 位,如果不足 100 位则用高位零补齐

Samples

input:
2 3 4 3 2 1
output:
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000026