#include "peru.h"
#include <iostream>
#include <deque>
#include <set>
#include <vector>
using namespace std;
int const mod=1e9+7;
int solve(int n, int k, int* v)
{
vector<long long>a;
a.push_back(2e9+10);
for (int i=0;i<n;i++)
a.push_back(v[i]);
long long dp[n+10]={};
dp[0]=0;
long long pw[n+10]={};
long long val[n+10]={};
pw[0]=1;
deque<long long>q;
for (int i=1;i<=n;i++)
{
dp[i]=1e18+10;
while (q.size()&&a[q.back()]<=a[i])
q.pop_back();
while (q.size()&&q.front()<=i-k)
q.pop_front();
q.push_back(i);
dp[i]=dp[max(0,i-k)]+a[q.front()];
for (int j=0;j+1<q.size();j++)
{
dp[i]=min(dp[q[j]]+q[j+1],dp[i]);
}
pw[i]=(pw[i-1]*23ll)%mod;
}
long long ans=0;
for (int i=1;i<=n;i++)
{
dp[i]%=mod;
ans=ans+(dp[i]*pw[n-i])%mod;
ans%=mod;
}
return ans;
}
