#include "peru.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
void add(int& a, int b){
if((a += b) >= mod){
a -= mod;
}
}
void mul(int& a, int b){
a = ll(a) * b % mod;
}
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 25e5 + 5;
const ll INF = 1e18;
int n, k, s[lim];
namespace sub1{
int solve(){
vector<ll>dp(n + 1, INF);
int ans = dp[0] = 0;
for(int i = 1; i <= n; i++){
for(int r = i, l = max(0, i - k), x = 0; r > l; r--){
maximize(x, s[r]);
minimize(dp[i], dp[r - 1] + x);
}
}
for(int i = n, c = 1; i > 0; i--, mul(c, 23)){
add(ans, dp[i] % mod * c % mod);
}
return ans;
}
}
namespace sub2{
const int lim = 4e5 + 5;
pair<int, ll>up[19][lim];
int solve(){
for(int i = 0; i < 19; i++){
up[i][0] = make_pair(0, INF);
}
vector<ll>dp(n + 1, INF);
s[dp[0] = 0] = INT_MAX;
stack<int>st;
st.push(0);
for(int i = 1; i <= n; st.push(i++)){
while(!st.empty() && s[st.top()] <= s[i]){
st.pop();
}
up[0][i] = make_pair(st.top(), dp[st.top()] + s[i]);
for(int j = 1; j < 19; j++){
up[j][i] = make_pair(up[j - 1][up[j - 1][i].first].first, min(up[j - 1][i].second, up[j - 1][up[j - 1][i].first].second));
}
int x = i;
for(int j = 18; j > -1; j--){
if(i - up[j][x].first <= k){
minimize(dp[i], up[j][x].second);
x = up[j][x].first;
}
}
if(i >= k){
minimize(dp[i], dp[i - k] + s[x]);
}
}
int ans = 0;
for(int i = n, c = 1; i > 0; i--, mul(c, 23)){
add(ans, dp[i] % mod * c % mod);
}
return ans;
}
}
namespace sub3{
deque<int>d;
ll dp[lim], vl[lim], vr[lim], ml[lim], mr[lim], tmp[lim];
int sl = 0, sr = 0, ans = 0;
void rebuild(bool isl){
int sz = 0;
for(int i = sl; i > 0; i--){
tmp[++sz] = vl[i];
}
for(int i = 1; i <= sr; i++){
tmp[++sz] = vr[i];
}
sr = sz - (sl = sz >> 1);
if(isl){
swap(sl, sr);
}
for(int i = 1; i <= sl; i++){
ml[i] = min(ml[i - 1], vl[i] = tmp[sl - i + 1]);
}
for(int i = 1; i <= sr; i++){
mr[i] = min(mr[i - 1], vr[i] = tmp[sl + i]);
}
}
void right_push(ll x){
vr[++sr] = x;
mr[sr] = min(mr[sr - 1], x);
}
void right_pop(){
if(sr == 0){
rebuild(false);
}
sr--;
d.pop_back();
}
void left_pop(){
if(sl == 0){
rebuild(true);
}
sl--;
d.pop_front();
}
int solve(){
ml[dp[0] = 0] = mr[0] = INF;
for(int i = 1; i <= n; d.push_back(i++)){
while(!d.empty() && i - d.front() > k){
left_pop();
}
while(!d.empty() && s[d.back()] <= s[i]){
right_pop();
}
if(!d.empty()){
int x = d.back();
right_pop();
d.push_back(x);
right_push(dp[x] + s[i]);
}
dp[i] = min(dp[max(0, i - k)] + s[d.empty() ? i : d.front()], min(ml[sl], mr[sr]));
right_push(0);
}
for(int i = n, c = 1; i > 0; i--, mul(c, 23)){
add(ans, dp[i] % mod * c % mod);
}
return ans;
}
}
int solve(int _n, int _k, int* _s){
for(int i = n = _n; i > 0; i--){
s[i] = _s[i - 1];
}
k = _k;
if(n <= 2000){
return sub1::solve();
}
if(n <= 400000){
return sub2::solve();
}
return sub3::solve();
}
