#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;

/*
 前から DP？それとも最大値分割？
 前から DP する. dp[最初の生存] = コストの最小値.
 dp は単調増加なので, dp[i-1] から更新できる位置を dp[i] から更新する必要はない.
 A[i] から, 「A[i] より先にある A[i] 以上の最初の要素」に辺を張り, これをたどりながら更新, すでに更新されていたら break して, dp[i+K] を更新
 
 1. A[i] から, 「A[i] より先にある A[i] 以上の最初の要素」に辺を張る (後ろから stack で管理)
 2. max(A[i:i+K]) をスライド最大値で計算
 3. DP する
 */
const ll MOD = 1000000007;
int solve(int N, int K, int* S) {
    vector<ll> nxt = [&]{
        vector<ll> nxt(N);
        vector<pair<ll, ll>> q;
        q.emplace_back(INF, N);
        for(ll i = N; i--; ) {
            while(q.back().first <= S[i]) q.pop_back();
            nxt[i] = q.back().second;
            q.emplace_back(S[i], i);
        }
        return nxt;
    }();
    vector<ll> mx = [&]{
        vector<ll> mx(N);
        deque<pair<ll, ll>> q;
        for(ll i = 0; i < N; i++) {
            if(q.size() && q.front().second <= i - K) q.pop_front();
            while(q.size() && q.back().first <= S[i]) q.pop_back();
            q.emplace_back(S[i], i);
            mx[i] = q.front().first;
        }
        mx.erase(mx.begin(), mx.begin() + K - 1);
        return mx;
    }();
    vector<ll> dp(N + 1, INF);
    dp[0] = 0;
    for(ll i = 0; i < N; i++) {
        if(dp[i] == INF) dp[i] = dp[nxt[i - 1]];
        if(i + K <= N) dp[i + K] = dp[i] + mx[i];
        ll j = i;
        while(j < N) {
            const ll k = nxt[j];
            if(k >= i + K || dp[k] != INF) break;
            dp[k] = dp[i] + S[j];
            j = k;
        }
    }
    ll ans = 0;
    for(ll i = 1; i <= N; i++) {
        ans *= 23;
        ans += dp[i];
        ans %= 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;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~