#include<bits/stdc++.h>
#include"peru.h"

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}

struct node{
	ll x;
	int l,r;
	node(ll x=0,int l=0,int r=0):x(x),l(l),r(r){}
	bool operator==(const node c)const{return x==c.x&&r==c.r;}
	bool operator<(const node c)const{return x==c.x?r<c.r:x>c.x;}
}q[2500005];

const int cys=1000000007;
int top,front,rear,mid;
int a[2500005],stk[2500005];
ll d[2500005],min1[2500005],min2[2500005];
priority_queue<node> q1,q2;

void rebuild(int l,int r){
	int mid=(l+r-1)/2;
	min1[mid+1]=min2[mid]=1ll<<60;
	for(int i=mid;i>=l;i--) min1[i]=min(min1[i+1],q[i].x);
	for(int i=mid+1;i<r;i++) min2[i]=min(min2[i-1],q[i].x);
}

void pop2(){
	rear--;
	if(mid==rear) rebuild(front,rear);
}

void pop1(){
	front++;
	if(front==mid+1) rebuild(front,rear);
}

void push2(node th){
	q[rear++]=th;
	if(front+1==rear) rebuild(front,rear);
	else min2[rear-1]=min(rear-2<=mid?(1ll<<60):min2[rear-2],th.x);
}

int solve(int n,int k,int *S){
	for(int i=0;i<n;i++) a[i+1]=S[i];
	d[0]=0;
	int cur=0;
	for(int i=1;i<=n;i++){
		// cout<<"################ "<<i<<endl;
		while(top&&a[stk[top]]<a[i]){
			if(stk[top-1]>=i-k-1){
				// cout<<"erase "<<stk[top-1]<<' '<<stk[top]<<' '<<d[stk[top-1]]+a[stk[top]]<<endl;
				// q2.push(node(d[stk[top-1]]+a[stk[top]],stk[top-1],stk[top]));
				if(front<rear&&q[rear-1].l==stk[top-1]) pop2();
			}
			top--;
		}
		// cout<<"insert "<<stk[top]<<' '<<i<<' '<<d[stk[top]]+a[i]<<endl;
		// q1.push(node(d[stk[top]]+a[i],stk[top],i));
		node th(d[stk[top]]+a[i],stk[top],i);
		if(front<rear&&q[rear-1].l==stk[top]) pop2();
		push2(th);
		stk[++top]=i;
		d[i]=1ll<<60;
		// while(!q1.empty()&&!q2.empty()&&q1.top()==q2.top()) q1.pop(),q2.pop();
		// while(!q1.empty()&&q1.top().l<i-k){
		// 	q1.pop();
		// 	while(!q1.empty()&&!q2.empty()&&q1.top()==q2.top()) q1.pop(),q2.pop();
		// }
		while(front<rear&&q[front].l<i-k) pop1();
		if(front<rear) chkmin(d[i],min(front<=mid?min1[front]:(1ll<<60),mid+1<rear?min2[rear-1]:(1ll<<60)));
		// for(int i=front;i<rear;i++) cout<<q[i].l<<' '<<q[i].r<<' '<<q[i].x<<endl;
		// if(!q1.empty()) chkmin(d[i],q1.top().x);
		chkmin(cur,top);
		while(stk[cur]<=i-k) cur++;
		if(i>=k) chkmin(d[i],d[i-k]+a[stk[cur]]);
	}
	// for(int i=1;i<=n;i++) cout<<d[i]<<' ';
	// cout<<endl;
	ll ret=0;
	for(int i=1;i<=n;i++) ret=(ret*23+d[i])%cys;
	return ret;
}