#include <bits/stdc++.h>
#include "peru.h"
using namespace std;
using i64 = long long;
const int MOD = 1e9 + 7;
i64 add(i64 x,i64 y){
return (x % MOD + y % MOD) % MOD;
}
i64 mul(i64 x,i64 y){
return (x % MOD * (y % MOD)) % MOD;
}
int solve(int n, int k, int* v){
vector<i64> dp(n + 10,2e18);
deque<i64> dq;
multiset<i64> st;
dp[0] = v[0];
dq.push_back(0);
for (int i = 1; i < n; i++){
while (!dq.empty() && v[i] >= v[dq.back()]){
int x = dq.back();
dq.pop_back();
if (!dq.empty()) st.erase(st.find(v[x] + dp[dq.back()]));
}
if (!dq.empty()) st.insert(v[i] + dp[dq.back()]);
dq.push_back(i);
while (!dq.empty() && dq.front() <= i - k){
int x = dq.front();
dq.pop_front();
st.erase(st.find(v[dq.front()] + dp[x]));
}
//for (auto x : dq) cerr << x << ",";
//cerr << endl;
if (st.size()) dp[i] = *st.begin();
if (!dq.empty()) dp[i] = min(dp[i],(i - k >= 0 ? dp[i - k] : 0) + v[dq.front()]);
}
i64 pw = 1,ans = 0;
for (int i = n-1; i > -1; i--){
ans = add(ans,mul(dp[i],pw));
pw = mul(pw,23);
}
/*for (int i = 0; i < n; i++){
cerr << dp[i] << " ";
}*/
return ans;
}
