Description

大家都知道睿爸最近一直都在玩风暴英雄，现在睿爸使用的是一个伤害非常高的角色。这个角色在打怪时会给怪物叠加一种名为“怒意狂击”的 魔法增益，能够有效增加他的伤害，这个 魔法增益 会让怪物每次受到的伤害增加 𝑥 而这个英雄最可怕的地方在于，这个魔法增益是可以叠加的，而且叠加效果呈几何形式增长！ 也就是当叠加了两次 怒意狂击 以后，怪物每次受到的伤害将会是 $𝑥^2$，当叠加了三次 怒意狂击 以后，怪物每次受到的伤害将会是 $𝑥^3$! 现在睿爸一顿操作以后只记得他对每种怪物在每次魔法增益状态下攻击了多少次,请你告诉他他总共造成了多少点伤害

Input

第一行包含两个整数 𝑥, 𝑛。𝑥 含义如题，𝑛 表示睿爸总共给怪物叠加了 𝑛 次 魔法增益

接下来 𝑛 + 1 行，第 𝑖 行一个整数$𝑎_𝑖$含义如下

$𝑎_0$表示除了 魔法增益 伤害以外睿爸总共造成了多少伤害

$𝑎_1$表示在 1层魔法增益状态下攻击了$𝑎_1$次...$𝑎_𝑛$表示在 𝑛层魔法增益状态下攻击了$𝑎_𝑛$次

Output

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

Samples

2 3
4
3
2
1

0000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000026

Limitation

对于 20% 的数据，1 ≤ 𝑛 ≤ 10

对于 50% 的数据，1 ≤ 𝑛 ≤ 200

对于 100% 的数据，1 ≤ 𝑛 ≤ 100000, 𝑥 ≤ 10,0 ≤ 𝑎𝑖 ≤ 100