#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int a[2500005];
int que[2500005],ql,qr;
long long dp[2500005];
long long sta1[2500005];
int top1;
long long min1[2500005];
long long sta2[2500005];
int top2;
long long min2[2500005];
void popfirst()
{
	if(top1>=1)top1--;
	else
	{
		int mid=(top2+1)/2;
		for(int i=mid;i>=1;i--)sta1[++top1]=sta2[i];
		for(int i=mid+1;i<=top2;i++)sta2[i-mid]=sta2[i];
		top2-=mid;
		min1[1]=sta1[1];
		for(int i=2;i<=top1;i++)min1[i]=min(min1[i-1],sta1[i]);
		min2[1]=sta2[1];
		for(int i=2;i<=top2;i++)min2[i]=min(min2[i-1],sta2[i]);
		top1--;
	}
}
void popback()
{
	if(top2>=1)top2--;
	else
	{
		int mid=(top1+1)/2;
		for(int i=mid;i>=1;i--)sta2[++top2]=sta1[i];
		for(int i=mid+1;i<=top1;i++)sta1[i-mid]=sta1[i];
		top1-=mid;
		min1[1]=sta1[1];
		for(int i=2;i<=top1;i++)min1[i]=min(min1[i-1],sta1[i]);
		min2[1]=sta2[1];
		for(int i=2;i<=top2;i++)min2[i]=min(min2[i-1],sta2[i]);
		top2--;
	}
}
void pushback(long long x)
{
	sta2[++top2]=x;
	if(top2==1)min2[top2]=x;
	else min2[top2]=min(x,min2[top2-1]);
}
long long findmin()
{
	long long ans=1000000000000000000LL;
	if(top1>=1)ans=min(ans,min1[top1]);
	if(top2>=1)ans=min(ans,min2[top2]);
	return ans;
}
int solve(int n,int k,int* S)
{
	for(int i=1;i<=n;i++)a[i]=S[i-1];
	ql=qr=1;
	que[1]=0;
	a[0]=2000000000;
	for(int i=1;i<=n;i++)
	{
		while(qr>=ql&&que[ql]<i-k)
		{
			if(ql<qr)popfirst();
			ql++;
		}
		while(qr>=ql&&a[que[qr]]<=a[i])
		{
			if(ql<qr)popfirst();
			qr--;
		}
		dp[i]=1000000000000000000LL;
		if(ql<=qr)pushback(dp[que[qr]]+a[i]);
		que[++qr]=i;
		dp[i]=findmin();
		if(i>=k)dp[i]=min(dp[i],dp[i-k]+a[que[ql]]);
		//printf("%d %d %d %lld\n",top1,top2,i,dp[i]); 
	}
	int ans=0;
	for(int i=1;i<=n;i++)ans=(23LL*ans+dp[i]%mod)%mod;
	return ans;
}