Beetle Bash Optimization

This is an interactive function problem.

There are \(N\) beetles arranged in a line from left to right with indices \(0\) to \(N-1\). The \(i\)th beetle has a strength of \(S_i\).

You can repeatedly choose a contiguous segment of at most \(K\) beetles and hit them with a force \(E\) (which can vary from hit to hit). When hit, a beetle dies if its strength is \(\le E\); otherwise, nothing happens. Note that once a beetle is killed it remains in place and can be hit again.

Define \(f(i)\) as the minimum total force needed to kill the leftmost \(i\) beetles (i.e. beetles with indices \(0,1,\dots,i-1\)). For each \(i=1,2,\dots,N\), you need to compute \(f(i)\).

To reduce the output size, you only need to output the value

\[ \left(\sum_{i=1}^{N} f(i) \cdot 23^{N-i}\right) \bmod (10^9+7), \]

Implement the following function:

int solve(int N, int K, int S[]);

The parameters are:

• N: the number of beetles.
• K: the maximum number of consecutive beetles you can hit in one move.
• S: an array representing the strength of each beetle.

The interactor will call solve exactly once.

Hint: The optimal strategy is to partition the first \(i\) beetles into segments (each of length at most \(K\)) and use one hit per segment with force equal to the maximum strength in that segment. Thus, \(f(i)\) is the minimum over all valid partitionings of \(\sum \max(S_j)\) for each segment.

inputFormat

The input is given as follows:

N K
S[0] S[1] ... S[N-1]

For example, for 3 beetles you might receive:

3 2
1 2 3

outputFormat

Output a single integer which is the value of

\[ \left(\sum_{i=1}^{N} f(i) \cdot 23^{N-i}\right) \bmod (10^9+7). \]

For the sample input above, the output would be 579.

sample

3 2
1 2 3

579

</p>