题目描述

Daniel13265 有一串由各种漂亮的贝壳组成的项链，但由于各种原因，这个项链不是环形的，而仅仅是用一根普通的丝线串起来的。项链上的每个贝壳都有一个好看程度 $a_i$，相同种类的贝壳有着相同的好看程度，而不同种类的贝壳有着不同的好看程度。

Danie13265 定义， 第 $l$ 个至第 $r$ 个这一段贝壳是对称的，当且仅当

Daniel13265 经常从中取出一段贝壳。如果这一段贝壳是对称的，他就会非常高兴；如果这一段贝壳不是对称的，那么他会将其中的某些贝壳替换成新的，以使得这一段贝壳成为对称的。一次替换可以任意地改变任何一个位置上贝壳的好看程度，但是过多的替换会使这一段贝壳脱离原本的模样，所以 Daniel13265 至多会进行 $k$ 次替换。如果一段贝壳在进行至多 $k$ 次替换后能够成为对称的，那么 Daniel13265 就称这一段贝壳是「可观赏的」。

Daniel13265 简单地将第 $l$ 个至第 $r$ 个这一「可观赏的」的贝壳段的「观赏指数」定义为

其中 $a_i$ 表示第 $i$ 个贝壳原本的好看程度。

他现在很好奇，在这个贝壳组成的项链中，「可观赏的」贝壳段中「观赏指数」的最大值。但是由于这个值可能很大，所以你只需要求出它对 $10^9+7$ 取模后的结果即可。

输入格式

输入共 $2$ 行。

第一行两个正整数 $n,k$，表示这个贝壳组成的项链中贝壳的数目与 Daniel13265 对一段贝壳最多进行替换的次数。
第二行 $n$ 个用单个空格隔开的正整数，第 $i$ 个数 $a_i$​ 表示项链上第 $i$ 个贝壳的好看程度。

输出格式

输出一行一个非负整数，表示「可观赏的」贝壳段中「观赏指数」的最大值对 $10^9+7$ 取模后的结果。

7 1
1 2 4 2 3 3 4

288

6 1
3 1 2 250000002 1 2

1

提示

样例解释 #1

「可观赏的」贝壳段有 $[1],[2],[3],[4],[1,2],[2,3],[2,4],[3,3],[3,4],[4,2],[1,2,4],[2,3,3],[2,4,2],[3,3,4],[4,2,3],[2,3,3,4],[4,2,3,3,4]$，其中「观赏指数」最大的贝壳段为 $[4,2,3,3,4]$。

样例解释 #2

「可观赏的」的贝壳段中「观赏指数」最大的为 $[2,250000002,1,2]$，其值为 $10^9+8$，对 $10^9+7$ 取模后结果为 $1$。

数据范围

本题采用捆绑测试。你每通过一个子任务的所有数据点，就能得到该子任务的全部分数。

对于 $100\%$ 的数据，满足 $1\le n\le1000$，$0\le k\le n$，$1\le a_i<10^9+7$。