放糖果

题目描述

给定一个长度为 $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 … A_{N-1}

输出格式

输出答案。

样例

5 3
2 1 6 3 1

11

盘子上糖果数量的变化如下。

第 $1$ 次操作时,$X=0$,所以再放入 $A_{(0\bmod 5)}=A_0=2$ 颗糖果。

第 $2$ 次操作时,$X=2$,所以再放入 $A_{(2\bmod 5)}=A_2=6$ 颗糖果。

第 $3$ 次操作时,$X=8$,所以再放入 $A_{(8\bmod 5)}=A_3=3$ 颗糖果。

因此,$3$ 次操作后盘子上有 $11$ 颗糖果。注意不要输出除以 $N$ 的余数。

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

826617499998784056

答案可能超出 $32$ 位整数类型的范围。

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le K \le 10^{12}$
• $1 \le A_i \le 10^6$
• 输入中的所有值均为整数。