该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

刚结束了 CS 战斗的小 D 又进入了 EVE 的游戏世界,在游戏中小 D 是一名商人,每天要做的事情就是在这里买东西,再运到那里去卖.这次小 D 来到了陌生的 X 星,X 星上有 n 种货物,小 D 决定每种都买走一些,他用 ai 来表示第 i 种货物购买的数量,X 星人对物品的单价有特别的决定方式。他们首先会选择一个基本价 x,第一种物品单价为 x,第二种物品单价为 x^2,第三种物品单价为 x^3……第 i 种物品单价为 x^i。结算总价时,你还需要给他们一笔手续费 a0,小 D 不知道自己带的钱是否能够进行这笔交易,所以请你帮助他计算这笔交易他要支付的总金额是多少。

Format

Input

x n

a0

a1

a2 . .

.an

第一行两个数分别表示基准价 x (x<=10),物品种数 n (n<=100000)

第二行一个数,手续费 a0 (a0<=100)

接下来的 n 行每行一个数,第 i 行表示第 i 种物品购买的数量(ai<=100)

Output

输出结果的最后 100 位,若不足 100 位请高位用零补足。

Samples

2 3
4
3
2
1

00000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000026

Limitation

对 20%的数据,n<=10

对 50%的数据,n<=200

对 100%的数据,n<=100000