AT_abc241_e [ABC241E] Putting Candies

题目描述

给你一个长度为 $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}$

输出格式

输出答案

样例 1

输入

5 3
2 1 6 3 1

输出

11

样例 2

输入

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$
• 输入都是整数