///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 LL Mod(LL x) {return x>=mod?x-mod:x;}
inline void addmod(LL &x,LL y) {x=Mod(x+y);}

LL n,k,a[N],f[N];
struct Desta
{
	LL 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 LL 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]});
	}
	LL 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;
	return 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 member function ‘void Desta::rebuild(int)’:
answer.code:37:77: error: no matching function for call to ‘min(long long int&, int)’
   37 |                 tp1=tp2=0; b[0]=n; if(t) return s1[++tp1]=b[1],pre1[tp1]=min(pre1[tp1-1],(int)1e9),void();
      |                                                                          ~~~^~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:2:
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)’
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
answer.code:37:77: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘int’)
   37 |                 tp1=tp2=0; b[0]=n; if(t) return s1[++tp1]=b[1],pre1[tp1]=min(pre1[tp1-1],(int)1e9),void();
      |                                                                          ~~~^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)’
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note:   template argument deduction/substitution failed:
answer.code:37:77: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘int’)
   37 |                 tp1=tp2=0; b[0]=n; if(t) return s1[++tp1]=b[1],pre1[tp1]=min(pre1[tp1-1],(int)1e9),void();
      |                                                                          ~~~^~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)’
 5775 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note:   template argument deduction/substitution failed:
answer.code:37:77: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
   37 |                 tp1=tp2=0; b[0]=n; if(t) return s1[++tp1]=b[1],pre1[tp1]=min(pre1[tp1-1],(int)1e9),void();
      |                                                                          ~~~^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)’
 5785 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note:   template argument deduction/substitution failed:
answer.code:37:77: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
   37 |                 tp1=tp2=0; b[0]=n; if(t) return s1[++tp1]=b[1],pre1[tp1]=min(pre1[tp1-1],(int)1e9),void();
      |                                                                          ~~~^~~~~~~~~~~~~~~~~~~~~~