#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;
long long fastpow(long long a , long long b){
long long ret = 1;
while(b){
if(b&1)ret = ret * a % mod;
a = a * a % mod;
b >>= 1;
}
return ret;
}
struct SEGTmax{
vector < int > t;
int tree_size;
const int identity_element = -inf;
int merge(int x , int y){
return max(x,y);
}
void init(int x){
tree_size = x+3;
t.assign(2*tree_size , identity_element);
}
void modify(int p, int value) { // set value at position p
for (t[p += tree_size] = value; p > 1; p >>= 1){
t[p>>1] = merge(t[p] , t[p^1]);
}
}
int query(int l, int r) { // sum on interval [l, r]
int res = identity_element;
for (r+=1 , l += tree_size, r += tree_size; l < r; l >>= 1, r >>= 1) {
if (l&1) res = merge(res , t[l++]);
if (r&1) res = merge(res , t[--r]);
}
return res;
}
};
struct SEGTmin{
vector < int > t;
int tree_size;
const int identity_element = inf;
int merge(int x , int y){
return min(x,y);
}
void init(int x){
tree_size = x+3;
t.assign(2*tree_size , identity_element);
}
void modify(int p, int value) { // set value at position p
for (t[p += tree_size] = value; p > 1; p >>= 1){
t[p>>1] = merge(t[p] , t[p^1]);
}
}
int query(int l, int r) { // sum on interval [l, r]
int res = identity_element;
for (r+=1 , l += tree_size, r += tree_size; l < r; l >>= 1, r >>= 1) {
if (l&1) res = merge(res , t[l++]);
if (r&1) res = merge(res , t[--r]);
}
return res;
}
};
int solve(int n, int k, int* v){
SEGTmax arr;
arr.init(n);
SEGTmin dp;
dp.init(n);
for(int i = 0;i<n;i++){
arr.modify(i , v[i]);
}
long long ans = 0;
dp.modify(0 , 0);
for(int i = 0;i<n;i++){
int val = arr.query(max(0,i-k+1) , i) + dp.query(max(0,i+1-k) , i);
// cout << "bruh : " << dp.query(max(0ll,i+1-k),i) << endl;
// cout << i+1 << " : " << val << endl;
dp.modify(i+1 , val);
ans = 1LL * (ans + 1LL * val * fastpow(23,n-i-1) % mod) % mod;
}
return ans;
}
// signed main(){
// int n,k;
// cin >> n >> k;
// int arr[n];
// for(int i = 0;i<n;i++)cin >> arr[i];
// cout << solve(n,k,arr) << endl;
// }
