#include <bits/stdc++.h>
#include "peru.h"
using namespace std;
const long long MOD = 1e9+7;
int mod_expo(long long a, long long e) {
if (e == 0) return 1;
if (e == 1) return a % MOD;
long long val = mod_expo(a/2, e);
long long extra = (a % 2 == 1 ? a : 1);
return (((val * val) % MOD) * extra) % MOD;
}
int32_t solve(int32_t n, int32_t k, int32_t* arr) {
// long long everywhere it matters
vector<long long> exponents(n);
exponents[0] = 1;
for(int i = 1; i < n; i++)
exponents[i] = (exponents[i-1] * 23) % MOD;
// dp uses long long, and initial value must be LLONG_MAX
vector<vector<long long>> dp(n, vector<long long>(k, LLONG_MAX));
dp[0][0] = arr[0];
for(int j = 1; j < k; j++)
dp[0][j] = max(dp[0][j-1], (long long)arr[j]);
for(int i = 1; i < n; i++) {
long long st_val = LLONG_MAX;
for(int j = 0; j < k; j++) {
if(i - 1 - j < 0) break;
st_val = min(st_val, dp[i-1-j][j]);
}
long long add = arr[i];
for(int j = 0; j < k; j++) {
if(i + j >= n) break;
add = max(add, (long long)arr[i+j]);
dp[i][j] = st_val + add; // no mod here!!
}
}
vector<long long> ans(n, LLONG_MAX);
for(int i = 0; i < n; i++) {
for(int j = 0; j < k; j++) {
if(i - j < 0) break;
ans[i] = min(ans[i], dp[i-j][j]);
}
}
long long mod_ans = 0;
for(int i = 0; i < n; i++) {
mod_ans = (mod_ans + (ans[i] % MOD) * exponents[n - i - 1]) % MOD;
}
return mod_ans;
}
