#include<bits/stdc++.h>
#include"peru.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2.5e5 + 5;
const int mod = 1e9 + 7;
const ll linf = 0x3f3f3f3f3f3f3f3f;

int a[MAXN];

int solve(int n, int d, int *_a)
{
	for(int i=1; i<=n; ++i)
		a[i] = _a[i-1];
	
	static ll f[MAXN];
	fill(f+1, f+n+1, linf);
	f[0] = 0;
	
	for(int i=1; i<=n; ++i)
	{
		int cur = 0;
		for(int j=i; j>=1 && j>=i-d+1; --j)
		{
			cur = max(cur, a[j]);
			f[i] = min(f[i], f[j-1] + cur);
		}
	}
	
	int ans = 0, curpw = 1;
	for(int i=n; i>=1; --i)
	{
		ans = (ans + (ll)f[i] %mod * curpw) %mod;
		curpw = (ll)curpw * 23 %mod;
	}
	return ans;
}