替换
题目描述
Daniel13265 有一串由各种漂亮的贝壳组成的项链,但由于各种原因,这个项链不是环形的,而仅仅是用一根普通的丝线串起来的。项链上的每个贝壳都有一个好看程度 $a_i$,相同种类的贝壳有着相同的好看程度,而不同种类的贝壳有着不同的好看程度。
Danie13265 定义, 第 $l$ 个至第 $r$ 个这一段贝壳是对称的,当且仅当
$$\sum_{i=l}^r\left(a_i-a_{l+r-i}\right)^2=0$$
Daniel13265 经常从中取出一段贝壳。如果这一段贝壳是对称的,他就会非常高兴;如果这一段贝壳不是对称的,那么他会将其中的某些贝壳替换成新的,以使得这一段贝壳成为对称的。一次替换可以任意地改变任何一个位置上贝壳的好看程度,但是过多的替换会使这一段贝壳脱离原本的模样,所以 Daniel13265 至多会进行 $k$ 次替换。如果一段贝壳在进行至多 $k$ 次替换后能够成为对称的,那么 Daniel13265 就称这一段贝壳是「可观赏的」。
Daniel13265 简单地将第 $l$ 个至第 $r$ 个这一「可观赏的」的贝壳段的「观赏指数」定义为
$$\prod_{i=l}^ra_i$$
其中 $a_i$ 表示第 $i$ 个贝壳**原本的好看程度**。
他现在很好奇,在这个贝壳组成的项链中,「可观赏的」贝壳段中「观赏指数」的最大值。但是由于这个值可能很大,所以你只需要求出它对 $10^9+7$ 取模后的结果即可。
输入输出格式
输入格式
输入共 $2$ 行。
第一行两个正整数 $n,k$,表示这个贝壳组成的项链中贝壳的数目与 Daniel13265 对一段贝壳最多进行替换的次数。
第二行 $n$ 个用单个空格隔开的正整数,第 $i$ 个数 $a_i$ 表示项链上第 $i$ 个贝壳的好看程度。
输出格式
输出一行一个非负整数,表示「可观赏的」贝壳段中「观赏指数」的最大值对 $10^9+7$ 取模后的结果。
输入输出样例
输入样例 #1
7 1
1 2 4 2 3 3 4
输出样例 #1
288
输入样例 #2
6 1
3 1 2 250000002 1 2
输出样例 #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$。
### 数据范围
**本题采用捆绑测试。你每通过一个子任务的所有数据点,就能得到该子任务的全部分数。**
| 子任务编号 | $n\le$ | $k\le$ | 分值 |
|:-:|:-:|:-:|:-:|
| $1$ | $10$ | $10$ | $10$ |
| $2$ | $100$ | $100$ | $20$ |
| $3$ | $1000$ | $0$ | $20$ |
| $4$ | $1000$ | $1000$ | $50$ |
| $5$ | $10^6$ | $0$ | $0$ |
对于 $100\%$ 的数据,满足 $1\le n\le1000$,$0\le k\le n$,$1\le a_i<10^9+7$。