P6297 Replacement.

Daniel13265 has a necklace made of various beautiful shells. For various reasons, this necklace is not a ring. Instead, the shells are simply threaded on an ordinary string. Each shell on the necklace has a beauty value $a_i$. Shells of the same type have the same beauty value, while shells of different types have different beauty values. Daniel13265 defines that the segment of shells from the $l$-th to the $r$-th is symmetric if and only if $$\sum_{i=l}^r\left(a_i-a_{l+r-i}\right)^2=0$$ Daniel13265 often takes out a segment of shells. If the segment is symmetric, he will be very happy. If the segment is not symmetric, he will replace some shells in it with new ones so that the segment becomes symmetric. One replacement can arbitrarily change the beauty value of the shell at any one position. However, too many replacements will make the segment lose its original look, so Daniel13265 will perform at most $k$ replacements. If a segment can become symmetric after at most $k$ replacements, then Daniel13265 calls this segment “viewable”. Daniel13265 simply defines the “viewing index” of the “viewable” shell segment from the $l$-th to the $r$-th as $$\prod_{i=l}^ra_i$$ where $a_i$ denotes the **original beauty value** of the $i$-th shell. Now he is curious about the maximum “viewing index” among all “viewable” shell segments in this necklace. Since this value may be very large, you only need to output the result modulo $10^9+7$.

The input consists of $2$ lines. The first line contains two positive integers $n,k$, denoting the number of shells on the necklace and the maximum number of replacements Daniel13265 may perform on a segment. The second line contains $n$ positive integers separated by single spaces. The $i$-th number $a_i$ denotes the beauty value of the $i$-th shell on the necklace.

Output one line containing one non-negative integer, representing the maximum “viewing index” among all “viewable” shell segments modulo $10^9+7$.

### Sample Explanation #1 The “viewable” shell segments are $[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]$. Among them, the segment with the maximum “viewing index” is $[4,2,3,3,4]$. ### Sample Explanation #2 Among the “viewable” shell segments, the one with the maximum “viewing index” is $[2,250000002,1,2]$. Its value is $10^9+8$, and after taking modulo $10^9+7$, the result is $1$. ### Constraints **This problem uses bundled testdata. For each subtask, you will get the full score of that subtask only if you pass all test cases in it.** | Subtask ID | $n\le$ | $k\le$ | Score | |:-:|:-:|:-:|:-:| | $1$ | $10$ | $10$ | $10$ | | $2$ | $100$ | $100$ | $20$ | | $3$ | $1000$ | $0$ | $20$ | | $4$ | $1000$ | $1000$ | $50$ | For $100\%$ of the testdata, $1\le n\le1000$, $0\le k\le n$, and $1\le a_i