题目描述

長さ $N$ の数列 $A=(A_0,A_1,\ldots,A_{N-1})$ が与えられます。
最初の時点では空の皿があり、高橋君は次の操作を $K$ 回繰り返します。

• 皿の中のアメの個数を $X$ とする。皿に $A_{(X\bmod\ N)}$ 個のアメを追加する。 ただし、$X\bmod\ N$ で $X$ を $N$ で割った余りを表す。

$K$ 回の操作の後で、皿の中には何個のアメがあるか求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $A_0$ $A_1$ $\ldots$ $A_{N-1}$

输出格式

答えを出力せよ。

题目大意

题目描述

给你一个长度为 $N$ 的数列$A$， $A=(A_0,A_1,\ldots,A_{N-1})$。 最初是空盘，高桥君会执行$K$次以下操作。

• 设盘子里有$X$ 颗糖。每次在盘中放入$A_{(X\bmod\ N)}$ 颗糖。 $X\bmod\ N$ 表示 $X$ 除以 $N$ 的余数。

求$K$次后盘子里糖的颗数。

输入格式

输入以以下形式从标准输入给出:

$N$ $K$ $A_0$ $A_1$ $\ldots$ $A_{N-1}$

输出格式

输出答案

提示

制約

• $2\ \leq\ N\ \leq\ 2\times\ 10^5$
• $1\ \leq\ K\ \leq\ 10^{12}$
• $1\ \leq\ A_i\leq\ 10^6$
• 输入都是整数

5 3
2 1 6 3 1

11

10 1000000000000
260522 914575 436426 979445 648772 690081 933447 190629 703497 47202

826617499998784056

提示

制約

• $2\ \leq\ N\ \leq\ 2\times\ 10^5$
• $1\ \leq\ K\ \leq\ 10^{12}$
• $1\ \leq\ A_i\leq\ 10^6$
• 入力はすべて整数である。

Sample Explanation 1

皿の中のアメの個数は次のように変化します。 - $1$ 回目の操作において、$X=0$ であるので、アメは $A_{(0\mod\ 5)}=A_0=2$ 個追加されます。 - $2$ 回目の操作において、$X=2$ であるので、アメは $A_{(2\mod\ 5)}=A_2=6$ 個追加されます。 - $3$ 回目の操作において、$X=8$ であるので、アメは $A_{(8\mod\ 5)}=A_3=3$ 個追加されます。 よって、$3$ 回の操作の後で、皿には $11$ 個のアメがあります。出力する値は $N$ で割った余りでは**ない**事に注意してください。

Sample Explanation 2

答えは $32$ bit 整数型に収まらない場合があります。