#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7, nx=3e6+5;
ll dp[nx], p[nx];
struct minstack
{
struct data
{
ll h, idx, vl, mn;
data(ll h, ll idx, ll vl, ll mn): h(h), idx(idx), vl(vl), mn(mn){}
};
stack<data> s;
void push(data x)
{
if (s.empty()) s.push(data(x.h, x.idx, x.vl, x.vl));
else s.push(data(x.h, x.idx, x.vl, min(s.top().mn, x.vl)));
}
void pop() {s.pop();}
bool empty() {return s.empty();}
void swap(minstack &o) {s.swap(o.s);}
data top() {return s.top();}
int size() {return s.size();}
};
struct mindeque
{
minstack l, r, tmp;
void rebalance()
{
bool sw=0;
if (r.empty()) sw=1, l.swap(r);
int sz=r.size()/2;
while (sz--) tmp.push(r.top()), r.pop();
while (!r.empty()) l.push(r.top()), r.pop();
while (!tmp.empty()) r.push(tmp.top()), tmp.pop();
if (sw) l.swap(r);
}
void push(ll h, ll idx, ll vl)
{
r.push(minstack::data(h, idx, vl, 0ll));
}
ll getmin()
{
if (l.empty()) return r.top().mn;
if (r.empty()) return l.top().mn;
return min(l.top().mn, r.top().mn);
}
minstack::data front()
{
if (l.empty()) rebalance();
return l.top();
}
minstack::data back()
{
if (r.empty()) rebalance();
return r.top();
}
void pop_front()
{
if (l.empty()) rebalance();
l.pop();
}
void pop_back()
{
if (r.empty()) rebalance();
r.pop();
}
bool empty() {return l.empty()&&r.empty();}
} dq;
deque<int> rl;
int solve(int n, int k, int* v){
ll res=0;
p[0]=1;
for (int i=1; i<=n; i++) p[i]=(p[i-1]*23)%mod;
dq.push(1e18, -1, v[0]);
for (int i=0; i<n; i++)
{
while (!dq.empty()&&i-dq.front().idx>k) dq.pop_front();
while (!dq.empty()&&dq.back().h<=v[i]) dq.pop_back();
//cout<<"front "<<dq.front().idx<<' '<<dq.front().mn<<'\n';
//cout<<"back "<<dq.back().idx<<' '<<dq.back().mn<<'\n';
while (!rl.empty()&&i-rl.front()>k) rl.pop_front();
while (!rl.empty()&&v[rl.back()]<=v[i]) rl.pop_back();
rl.push_back(i);
if (!dq.empty())
{
auto tmp=dq.back();
dq.pop_back();
tmp.vl=tmp.idx>=0?dp[tmp.idx]+v[i]:v[i];
//cout<<"tmp "<<tmp.h<<' '<<tmp.idx<<' '<<tmp.vl<<'\n';
dq.push(tmp.h, tmp.idx, tmp.vl);
dp[i]=dq.getmin();
}
else dp[i]=LLONG_MAX;
//cout<<"bf "<<dp[i]<<'\n';
dp[i]=min(dp[i], i<k?v[rl.front()]:dp[i-k]+v[rl.front()]);
if (i<n-1) dq.push(v[i], i, dp[i]+v[i+1]);
res=(res+p[n-i-1]*(dp[i]%mod))%mod;
//cout<<"debug "<<i<<' '<<dp[i]<<'\n';
}
return res;
}
