#include "peru.h"

#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;++i)
#define per(i,a,b) for(int i=(a),i##end=(b);i>=i##end;--i)
mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
template<typename T>void chkmax(T&x,const T&y){if(x<y)x=y;}
template<typename T>void chkmin(T&x,const T&y){if(y<x)x=y;}

#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define mem(x) memset((x),0,sizeof(x))

typedef double db;
typedef long long ll;
typedef vector<int>vi;
typedef pair<int,int>pii;

typedef unsigned u32;
typedef unsigned uint;
typedef unsigned long long u64;

const int P=1e9+7;
const ll inf=1e18;

const int maxn=2.5e6+10;
int a[maxn];

ll dp[maxn];

struct node{
  ll f;
  int v,pos;
  ll get()const{
    return f+v;
  }
  bool operator<(const node&o)const{
    return get()<o.get()||(get()==o.get()&&pos>o.pos);
  }
};

struct zzh{
  vector<node>lef,l_pre,rig,r_pre;
  bool empty()const{
    return lef.empty()&&rig.empty();
  }
  node front()const{
    return lef.empty()?rig[0]:lef.back();
  }
  node back()const{
    return rig.empty()?lef[0]:rig.back();
  }
  void push_front(node o){
    lef.pb(o);
    l_pre.pb(l_pre.empty()?o:min(l_pre.back(),o));
  }
  void push_back(node o){
    rig.pb(o);
    r_pre.pb(r_pre.empty()?o:min(r_pre.back(),o));
  }
  vector<node>buf;
  void rebuild(){
    int cnt=buf.size()/2;
    rep(i,0,cnt-1){
      lef.pb(buf[iend-i]);
      l_pre.pb(i?min(l_pre.back(),buf[iend-i]):buf[iend-i]);
    }
    rep(i,cnt,buf.size()-1){
      rig.pb(buf[i]);
      r_pre.pb(i>cnt?min(r_pre.back(),buf[i]):buf[i]);
    }
  }
  void pop_back(){
    if(!rig.empty()){
      rig.pop_back(),r_pre.pop_back();return;
    }
    buf.resize(lef.size()-1);
    rep(i,0,lef.size()-2)buf[i]=lef[iend-i+1];
    lef.clear(),l_pre.clear();
    rebuild();
  }
  void pop_front(){
    if(!lef.empty()){
      lef.pop_back(),l_pre.pop_back();return;
    }
    buf.resize(rig.size()-1);
    rep(i,0,rig.size()-2)buf[i]=rig[i+1];
    rig.clear(),r_pre.clear();
    rebuild();
  }
  ll ask()const{
    return min(l_pre.empty()?inf:l_pre.back().get(),r_pre.empty()?inf:r_pre.back().get());
  }
}q;

int solve(int n, int k, int* v){
  rep(i,1,n)a[i]=v[i-1],dp[i]=inf;
  rep(i,1,n){
    ll ths=dp[i-1];
    while(!q.empty()&&q.back().v<=a[i]){
      chkmin(ths,q.back().f);
      q.pop_back();
    }
    q.push_back({ths,a[i],i});
    if(i-q.front().pos>=k){
      q.pop_front();
    }
    node lst=q.front();
    q.pop_front();
    q.push_front({dp[i-k],lst.v,lst.pos});
    
    dp[i]=q.ask();
    
//    printf("%d : %lld\n",i,dp[i]);
    
//    int mx=0;
//    per(j,i-1,max(0,i-k)){
//      chkmax(mx,a[j+1]);
//      chkmin(dp[i],dp[j]+mx);
//    }
  }
  int res=0;
  rep(i,1,n)res=(23ll*res+dp[i])%P;
  return res;
}

//#include"grader.cpp"