#include <bits/stdc++.h>
#include "peru.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const int m=23,dv=1e9+7;
const long long inf=1e18;
int d,nn=0,a[2500069],sk[2500069],fh[2500069],sr[2500069];
long long dp[2500069];
vector<int> al[2500069];
deque<pair<int,long long>> dq;
bitset<2500069> spc;
void bd(int x)
{
int i,sz=al[x].size(),l;
fh[x]=x;
for(i=0;i<sz;i++)
{
l=al[x][i];
bd(l);
fh[x]=max(fh[x],fh[l]);
}
}
void dfs(int x,long long cw)
{
int i,sz=al[x].size(),l;
dp[x]=min(cw,dp[max(x-d,0)]+a[sr[x]]);
for(;!dq.empty()&&dq.front().fr<x-d;dq.pop_front());
if(!dq.empty())
{
dp[x]=min(dp[x],dq.front().sc);
}
for(i=0;i<sz;i++)
{
l=al[x][i];
if(fh[l]-d>x)
{
for(;!dq.empty()&&dq.back().sc>=dp[x]+a[l];dq.pop_back());
dq.push_back({x,dp[x]+a[l]});
dfs(l,cw);
}
else
{
dfs(l,min(cw,dp[x]+a[l]));
}
}
}
int solve(int n,int od,int* aa)
{
int i,j,ml=1,z=0;
d=od;
for(j=0,i=1;i<=n;i++)
{
a[i]=aa[i-1];
for(;nn&&a[sk[nn]]<=a[i];nn--)
{
spc[sk[nn]]=0;
}
al[sk[nn]].push_back(i);
nn++;
sk[nn]=i;
spc[i]=1;
for(;j<=i-d||!spc[j];j++);
sr[i]=j;
}
bd(0);
dfs(0,inf);
for(i=n;i;i--)
{
z=(z+dp[i]%dv*ml)%dv;
ml=(long long)ml*m%dv;
}
return z;
}
