#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<bitset>
#include<cassert>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(((long long)(n))-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();++itr)
#define pb push_back
#define mk make_pair
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define spln(i,n) (i==n?'\n':' ')
#define fac_init(n){fac[0]=fac[1]=inv[1]=fi[0]=fi[1]=1;fz(i,2,n){fac[i]=1ll*fac[i-1]*i%mod;inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;fi[i]=1ll*fi[i-1]*inv[i]%mod;}}
using namespace std;
typedef long long i64;
typedef long double f80;
typedef unsigned int u32;
typedef unsigned long long u64;
//typedef __int128 i128;
//typedef unsigned __int128 u128;
const int mod=1e9+7;
int n,k,i,j,a[2500005];
i64 f[2500005];
struct deque
{
	i64 qx[5000005];int ql,qr;
	void init(){ql=2500001;qr=2500000;}
	void push_back(int x)
	{
		qx[++qr]=x;
	}
	void push_front(int x)
	{
		qx[--ql]=x;
	}
	void pop_back()
	{
		qr--;
	}
	void pop_front()
	{
		ql++;
	}
	int query()
	{
		i64 s=0x3f3f3f3f3f3f3f3fll;int i;
		fz(i,ql,qr) s=min(s,qx[i]);
		return s;
	}
}dq;
int qx[2500005],ql,qr;
int hd[2500005],tl[2500005];
i64 hdv[2500005],tlv[2500005];
int pre[2500005],suf[2500005];i64 dlt[2500005];
int solve(int nn,int kk,int *aa)
{
	n=nn;k=kk;fz1(i,n)a[i]=aa[i-1];
	ql=1;qr=0;dq.init();
	fz1(i,n){
		hd[i]=tl[i]=i;hdv[i]=tlv[i]=a[i]+f[i-1];
		while(ql<=qr&&a[qx[qr]]<=a[i]){
			hdv[qx[qr]]+=a[i]-a[qx[qr]];
			tlv[qx[qr]]+=a[i]-a[qx[qr]];
			while(tl[qx[qr]]&&tlv[qx[qr]]>=hdv[i]){
				tlv[qx[qr]]-=dlt[tl[qx[qr]]];
				suf[tl[qx[qr]]=pre[tl[qx[qr]]]]=0;
			}
			if(tl[qx[qr]]){
				suf[tl[qx[qr]]]=hd[i];pre[hd[i]]=tl[qx[qr]];
				dlt[hd[i]]=hdv[i]-tlv[qx[qr]];hdv[i]=hdv[qx[qr]];hd[i]=hd[qx[qr]];
			}
			dq.pop_back();qr--;
		}
		qx[++qr]=i;dq.push_back(hdv[i]);
		while(ql<=qr&&qx[ql]<=i-k) ql++,dq.pop_front();
		assert(ql<=qr);
		while(hd[qx[ql]]<=i-k){
			dq.pop_front();
			hd[qx[ql]]=suf[hd[qx[ql]]];hdv[qx[ql]]+=dlt[hd[qx[ql]]];
			dq.push_front(hdv[qx[ql]]);
		}
		f[i]=dq.query();
	}
//	fz1(i,n)cerr<<f[i]<<' ';cerr<<endl;
	int ans=0;fz1(i,n)ans=(23ll*ans+f[i])%mod;return ans;
}