#include <bits/stdc++.h>

using namespace std;
#include "peru.h"

long long seg[2500000*4];
long long mod = 1000000007;
void update(int p,int l,int r,int idx,int val){
    if(l==r){
        seg[p] = val;
        return ;
    }
    int md = (l+r)/2;
    if(idx<=md)update(p*2,l,md,idx,val);
    else update(p*2+1,md+1,r,idx,val);
    seg[p] = min(seg[p*2],seg[p*2+1]);
}
long long query(int p,int l,int r,int lq,int rq){
    if(l>=lq&&r<=rq)return seg[p];
    if(r<lq||l>rq)return 1e18;
    int md = (l+r)/2;
    return min(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
int solve(int n, int k,int* ss){
    int arr[n+1];
    for(int i = 1;i<=n*4;i++)seg[i] = 1e18;
    for(int i = 1;i<=n;i++)arr[i] = ss[i-1];
    long long dp[n+1] = {0};
    update(1,0,n,0,0);
    multiset<long long> s;
    deque<pair<long long,long long>> st;
    for(int i = 1;i<=n;i++){
        long long mi = dp[i-1];
        while(!st.empty()&&arr[st.back().second]<=arr[i]){
            s.erase(s.lower_bound(st.back().first+arr[st.back().second]));
            mi = min(mi,st.back().first);
            st.pop_back();
        }
        st.push_back({mi,i});
        s.insert(mi+arr[i]);
        int la = 0;
        while(!st.empty()&&st[0].second<=i-k){
            cout<<st[0].second<<endl;
            la = st[0].second;
            s.erase(s.lower_bound(arr[st[0].second]+st[0].first));
            st.pop_front();
        }
        if(la<i-k){
        int e = st[0].second;
        s.erase(s.lower_bound(arr[e]+st[0].first));
        st.pop_front();
        long long vl = query(1,0,n,i-k,e-1);
        s.insert(arr[e]+vl);
        st.push_front({vl,e});
        }
        dp[i] =(*s.begin());
        update(1,0,n,i,dp[i]);
    }
    long long ans = 0 , po = 1;
    for(int i = n;i>=1;i--){
        ans+=(dp[i]*po)%mod;ans%=mod;
        po*=23;po%=mod;
    }
    return ans;
}