///yl/hs/bx/yl
#include<bits/stdc++.h>
#define fep(i,l,r) for(int i=l;i<=r;++i)
#define feb(i,r,l) for(int i=r;i>=l;--i)
#define For(i,u) for(int i=head[u];i;i=e[i].nxt)
#define LL long long
#define int long long
#define ld long double
#define pr pair<int,int>
#define mpr make_pair
using namespace std;

const int N = 2.5e6+5,mod = 1e9+7;
inline int read()
{
   int s=0,w=1; char ch=getchar();
   while(!(ch>='0'&&ch<='9')) {if(ch=='-') w=-1; ch=getchar();}
   while(  ch>='0'&&ch<='9')  {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
   return s*w;
}
inline int Mod(int x) {return x>=mod?x-mod:x;}
inline void addmod(int &x,int y) {x=Mod(x+y);}

int n,k,a[N],f[N];
struct Desta
{
	int pre1[N],pre2[N],b[N],s1[N],s2[N],tp1,tp2,cnt;
	inline bool empty() {return tp1+tp2==0;}
	inline void push(int x) {s2[++tp2]=x; pre2[tp2]=f[x-1]+a[x];}
	inline int Max() {return a[tp1?s1[tp1]:s2[1]];}

	inline void rebuild(int t)
	{
		cnt=0;
		feb(i,tp1,1) b[++cnt]=s1[i];
		fep(i,1,tp2) b[++cnt]=s2[i];
		tp1=tp2=0; b[0]=n; if(t) return s1[++tp1]=b[1],pre1[tp1]=min(pre1[tp1-1],(int)1e9),void();
		feb(i,cnt/2,1)     s1[++tp1]=b[i],pre1[tp1]=min(pre1[tp1-1],f[b[i-1]+1]+a[b[i]]);
		fep(i,cnt/2+1,cnt) s2[++tp2]=b[i],pre2[tp2]=min(pre2[tp2-1],f[b[i-1]+1]+a[b[i]]);
	}

	inline bool popback(int x)
	{
		if(empty()) return 0;
		if(!tp2) rebuild(0);
		if(a[s2[tp2]]<=a[x]) return --tp2,1;
		return 0;
	}

	inline bool popfront(int x)
	{
		if(empty()) return 0;
		if(!tp1) rebuild(1);
		if(x-s1[tp1]+1>k) return --tp1,1;
		return 0;
	}
}s;
int solve(int N,int K,int *S)
{
	n=N,k=K; s.pre1[0]=s.pre2[0]=f[n+1]=1e9;
	fep(i,1,n) a[i]=S[i-1];
	f[1]=a[1]; s.push(1);
	fep(i,2,n)
	{
		while(s.popfront(i)) ; while(s.popback(i)) ; s.push(i);
		f[i]=f[max(0ll,i-k)]+s.Max();// cerr<<s.tp1<<" "<<s.tp2<<"\n";
		if(!s.empty()) f[i]=min({f[i],s.pre1[s.tp1],s.pre2[s.tp2]});
	}
	int pw=1,ans=0;
//    fep(i,1,n) cerr<<f[i]<<" "; cerr<<"\n";
	fep(i,1,n) f[i]%=mod;
	feb(i,n,1)  addmod(ans,1ll*pw*f[i]%mod),pw=23ll*pw%mod;
	printf("%lld\n",ans);
}

implementer.cpp: In function ‘char nextch()’:
implementer.cpp:15:31: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   15 |     if (pos == BUF_SIZE) fread(buf, BUF_SIZE, 1, fin), pos = 0;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
answer.code: In function ‘long long int solve(long long int, long long int, long long int*)’:
answer.code:74:1: warning: no return statement in function returning non-void [-Wreturn-type]
   74 | }
      | ^
/usr/bin/ld: /tmp/ccjN935x.o: in function `main':
implementer.cpp:(.text.startup+0x151): undefined reference to `solve(int, int, int*)'
collect2: error: ld returned 1 exit status