P6297 替换

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$ 取模后的结果即可。

无

无

### 样例解释 #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