#11. 农场主FVV

农场主FVV

题目描述

众所周知,FVV是一个“农场主”,他一开始有一个连招(有 nn 段攻击),连招的第 ii 段攻击都有一个伤害 aia_i,现在他觉得这连招太弱了,他将要按照一下方法改进连招:

  • 新连招在原连招的基础上,在最后添加原连招的最后一段。
  • 在新连招后面添加原连招(除了最后一段)

重复上述方法,直到连招段数大于等于 mm,输出第 mm 段的伤害。

输入格式

第一行两个正整数,nnmm

第二行 nn 个正整数,aia_i

输出格式

输出第 mm 段的伤害

输入输出样例 #1

输入 #1

3 8
1 2 3

输出 #1

1

说明/提示

对于样例,第一次改进后变成 (1,2,3,3,1,2)(1,2,3,3,1,2),第二次改进后变成 (1,2,3,3,1,2,2,1,2,3,3,1)(1,2,3,3,1,2,2,1,2,3,3,1),第 mm 段伤害是 11

$1 \le n \le 2\times 10^6,1 \le m \le 10^{18},1 \le a_i \le 10^9+7$