#include "peru.h"
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
typedef long long ll;
const ll inf=1e18;
const ll p=1e9+7;
int n,k,a[N]; 
ll f[N]; int q[N],l,r;
ll st1[N],st2[N]; int tp1,tp2;
ll mn1[N],mn2[N];

void rebuild()
{
    int mid=(tp1+tp2)>>1,s=tp1+tp2;
    reverse(st1+1,st1+tp1+1);
    for(int i=1;i<=tp2;i++) st1[++tp1]=st2[i];
    tp2=0;
    for(int i=mid+1;i<=s;i++) st2[++tp2]=st1[i];
    tp1=mid; reverse(st1+1,st1+tp1+1);
    for(int i=1;i<=tp1;i++) mn1[i]=min(mn1[i-1],st1[i]);
    for(int i=1;i<=tp2;i++) mn2[i]=min(mn2[i-1],st2[i]);
}

void push_back(ll w)
{
    st2[++tp2]=w;
    mn2[tp2]=min(mn2[tp2-1],w);
}

void pop_back()
{
    if(!tp2) rebuild();
    tp2--;
}

ll cal_min() {return min(mn1[tp1],mn2[tp2]);}

void pop_front()
{
    if(!tp1) rebuild();
    tp1--;
}

int solve(int N,int K,int* S)
{
    //freopen("test.out","w",stdout);
    n=N; k=K;
    for(int i=1;i<=n;i++) a[i]=S[i-1];
    for(int i=1;i<=n;i++) f[i]=inf;
    mn1[0]=mn2[0]=inf;
    f[0]=0;
    a[0]=2e9+1; r=-1;
    for(int i=1;i<=n;i++)
    {
        assert(q[l]<=n);
        while(l<=r&&a[i]>=a[q[r]]) pop_back(),r--;
        while(l<=r&&i-q[l]>=k) pop_front(),l++;
        if(tp1||tp2) pop_back(),push_back(f[q[r]]+a[i]);
        q[++r]=i; f[i]=cal_min();
        f[i]=min(f[i],f[max(0,i-k)]+a[q[l]]);
        push_back(f[i]);
    }
    int ans=0,pw=1;
    for(int i=n;i>=1;i--)
    {
        f[i]%=p;
        int res=1ll*f[i]*pw%p;
        ans=1ll*(ans+res)%p;
        pw=23ll*pw%p;
    }
    return ans;
}