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

题目背景

夜幕降临，繁星低垂。

你来到了位于贝洛伯格下城区的一间 9 吧。这里灯红酒绿、推杯换盏。整个贝洛伯格的灰色、黑色、红色、白色，都在这里齐聚一堂。至于为什么是 9 吧而不是酒吧？可能是因为未成年人禁止喝酒吧。

“您好。”

一个神秘的男人向你打了招呼。

“介意吗？”

他指了指你旁边的位子。

你耸了耸肩。他缓缓坐下。在点了一杯 114# 汽油拌混凝土后，他开始向你讲述他的过去。他自称是曾经历过「边星贸易战争」、「第一次反有机战争」、「第二次帝皇战争」的、※终末※ 的使者。此次，是为你而来。

“财富、名望、梦想…”，他笑了笑，“你究竟想要什么？”

他想与你玩一个游戏。这个游戏的名字，便是《超高速拉格朗日插值法》。

题目描述

《超高速拉格朗日插值法》玩法如下。

首先，这位使者会准备一个序列 $\{a\}$。这个序列的第 $i$ 项可以被如此描述：

其中 $p,q,w$ 均为固定的值，但使者不会告诉你他们具体是多少。

之后，这位使者会向你展示这个序列的前 $k$ 项，即 $a_1,a_2,a_3,...,a_k$。

最后，他会给出一个命运的数字 $n$。你需要回答他，这个序列的第 $n$ 项是多少。正如你回答命运那样。

输入格式

第 $1$ 行共两个正整数 $n,k(k\geq 3)$，含义见【题目描述】。

第 $2$ 行共 $k$ 个整数，分别表示 $a_1,a_2,...,a_k$。

输出格式

共 $1$ 行一个整数，表示 $a_n$ 的值。

样例 1

输入

5 3
6 11 18 

输出

38

样例解释

易得 $p = 1, q = 2, w = 3$。因此 $a_5=25+10+3=38$。

样例 2

输入

20 7
418 704 1102 1612 2234 2968 3814 

输出

25004

样例 3

输入

ex_a.in

ex_a.out

数据范围

对于前 $10\%$ 的数据，保证 $p=q=0$，$3\le n\le 10$。

对于前 $30\%$ 的数据，保证 $p=0$，$3\le n\le 100$。

对于前 $60\%$ 的数据，保证 $3\le n\le 10^4$。

对于全部 $100\%$ 的数据，保证 $3\le k\le n\le 10^7$，$-3\times 10^4 \le p,q,w\le 3\times 10^4$。