说明

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

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

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

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

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

输入格式

第一行包含两个整数 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

输出格式

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

样例

2 3
4
3
2
1

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000026