Problem Description

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

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

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$.

Input Format

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 Format

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

7 1
1 2 4 2 3 3 4

288

6 1
3 1 2 250000002 1 2

1

Hint

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.

For $100\%$ of the testdata, $1\le n\le1000$, $0\le k\le n$, and $1\le a_i<10^9+7$.

Translated by ChatGPT 5