#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],INF = 1e18;
struct Desta
{
	LL pre1[N],pre2[N],b[N],s1[N],s2[N],tp1,tp2,cnt;
	inline bool empty() {return tp1+tp2==0;}
	inline int Max() {return a[tp1?s1[tp1]:s2[1]];}
	// inline void push(int x) {s2[++tp2]=x; pre2[tp2]=f[x-1]+a[x];}
	inline void push(int x)
	{
		s2[++tp2]=x;
		if(tp2==1) pre2[tp2]=(tp1?f[s1[1]]+a[x]:INF);
		else pre2[tp2]=min(pre2[tp2-1],f[s2[tp2-1]]+a[x]);
	}

	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+1; if(t&&cnt==1) return s1[++tp1]=b[1],pre1[tp1]=min(pre1[tp1-1],INF),void();
		feb(i,cnt/2,1)     s1[++tp1]=b[i],pre1[tp1]=min(pre1[tp1-1],f[b[i-1]]+a[b[i]]);
		fep(i,cnt/2+1,cnt) s2[++tp2]=b[i],pre2[tp2]=min(pre2[tp2-1],f[b[i-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,pre1[tp1]=tp1>=1?pre1[tp1-1]:INF,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]=INF;
	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();
		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 ‘int main()’:
implementer.cpp:34:13: error: ‘fout’ was not declared in this scope; did you mean ‘out’?
   34 |     fprintf(fout, "%d\n", sol);
      |             ^~~~
      |             out
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;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~