#include <bits/stdc++.h>
using namespace std;
//~ #define int long long
const int mod = 1e9+7;
int solve(int N, int K, int* S) {
vector<long long> dp(N+1, 0);
long long ans = 0;
deque<pair<int, int>> dq;
dq.push_front({0, -1});
for (int i = 0; i < N; i++) {
while (dq.size() && dq.back().first <= S[i]) dq.pop_back();
dq.push_back({S[i], i});
while (dq.size() && dq.front().second < i-K) dq.pop_front();
int prev = max(0, i-K+1);
dp[i+1] = dp[prev]+dq.front().first;
//~ cout << dp[i+1] << endl;
ans = ((long long)ans*23)%mod;
ans = (ans+dp[i+1])%mod;
}
//~ cout << ans << endl;
return ans;
}
//~ signed main() {
//~ ios::sync_with_stdio(false);
//~ cin.tie(0);
//~ cout.tie(0);
//~ vector<int> tmp = {3, 2, 9, 8, 7, 11, 3, 4};
//~ solve(8, 3, tmp);
//~ }
