#include "peru.h"
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,k,f[2500009],dp[2500009],mod=1000000007LL,xr[2500009],pas,P=23;
int PAS;
int solve(int nn, int kk, int* vv){
a=nn;k=kk;
for(i=1; i<=a; i++){
f[i]=(*vv);if(i!=a) vv++;
}
xr[0]=1;
for(i=1; i<=a+1; i++){
xr[i]=xr[i-1]*P;xr[i]%=mod;
}
for(i=1; i<=k; i++){
dp[i]=max(dp[i-1],f[i]);
}
for(i=k+1; i<=a; i++){
dp[i]=dp[i-1]+f[i];zx=f[i];
for(j=i-1; j>=i-k; j--){
dp[i]=min(dp[i],dp[j]+zx);
zx=max(zx,f[j]);
}
}
for(i=1; i<=a; i++){
pas+=dp[i]*xr[a-i];pas%=mod;
}
PAS=pas;return PAS;
}
