Maximum Aesthetic Segment Product

Daniel13265 has a necklace made up of various beautiful shells. Unlike a circular necklace, the shells are strung in a linear order on a thread. Each shell has a beauty value \(a_i\). Shells of the same type have the same beauty value, and different shells have different beauty values.

He defines a segment of shells from the \(l\)th to the \(r\)th shell to be symmetric if and only if

[ \sum_{i=l}^{r} (a_i - a_{l+r-i})^2 = 0, ]

which is equivalent to saying that for every index in the segment, \(a_i = a_{l+r-i}\) (i.e. the segment is a palindrome).

Often Daniel13265 chooses a segment of shells. If the segment is already symmetric, he is very happy. Otherwise, he may perform at most \(k\) replacements where in a single replacement he can change the beauty value of any shell arbitrarily, in order to make the segment symmetric. If a segment can be made symmetric after at most \(k\) replacements, he calls it scenic.

The scenic index of a scenic segment from \(l\) to \(r\) is defined as the product of the original beauty values of the shells in that segment:

[ \prod_{i=l}^{r} a_i, ]

Your task is to find the maximum scenic index among all scenic segments in the necklace, and output the result modulo \(10^9+7\).

Note: For a segment, the minimum number of replacements required to make it symmetric equals the number of mismatched symmetric pairs, i.e. the number of indices \(i\) (with \(l \le i \le \frac{l+r}{2}\)) such that \(a_i \neq a_{l+r-i}\). This number must not exceed \(k\) for the segment to be considered scenic.

inputFormat

The first line contains two integers \(n\) and \(k\) where \(n\) is the number of shells in the necklace and \(k\) is the maximum number of replacements allowed.

The second line contains \(n\) positive integers \(a_1, a_2, \ldots, a_n\), representing the beauty values of the shells.

It is guaranteed that \(1 \le n \le 1000\) and \(0 \le k \le 500\). (Note: The constraints are set so that a \(O(n^2)\) solution is acceptable.)

outputFormat

Output a single integer: the maximum scenic index modulo \(10^9+7\).

sample

3 0
1 2 1

2

</p>