#include <bits/stdc++.h>
#ifndef test
#include "peru.h"
#endif
using namespace std;
using ll = long long;
#define N 2500010
#define mod 1000000007ll
ll f[N];
int* s;
struct deq {
  int stk[2][N], top[2];
  ll minn[2][N];
  deq() {minn[0][0] = minn[1][0] = 1e18;}
  bool empty() const {return !(top[0] + top[1]);}
  int front() const {
    assert(!empty());
    if (top[0]) return stk[0][top[0]];
    return stk[1][1];
  }
  int back() const {
    assert(!empty());
    if (top[1]) return stk[1][top[1]];
    return stk[0][1];
  }
  void pb(int x, ll v) {
    stk[1][++top[1]] = x;
    minn[1][top[1]] = min(v, minn[1][top[1] - 1]);
  }
  void pf(int x, ll v) {
    stk[0][++top[0]] = x;
    minn[0][top[0]] = min(v, minn[0][top[0] - 1]);
  }
  ll getmin() const { return min(minn[0][top[0]], minn[1][top[1]]); }
  void rebuild(int flg = 0) {
    int siz = top[0] + top[1];
    int mid = (siz + flg) / 2;
    vector<int> tmp;
    for (int i = top[0]; i; --i) tmp.emplace_back(stk[0][i]);
    for (int i = 1; i <= top[1]; ++i) tmp.emplace_back(stk[1][i]);
    top[0] = top[1] = 0;
    for (int i = mid - 1; ~i; --i) {
      if (empty()) pf(tmp[i], 1e18);
      else pf(tmp[i], f[tmp[i]] + s[front()]);
    }
    for (int i = mid; i < siz; ++i) {
      if (empty()) pb(tmp[i], 1e18);
      else pb(tmp[i], f[back()] + s[tmp[i]]);
    }
  }
  void pop_front() {
    assert(!empty());
    if (!top[0]) rebuild(1);
    --top[0];
    if (!empty() && !top[0]) rebuild(1);
  }
  void pop_back() {
    assert(!empty());
    if (!top[1]) rebuild();
    --top[1];
  }
}q;
int solve(int n, int k, int* s) {
  ::s = s;
  ll res = 0;
  for (int i = 0; i < n; ++i) {
    if (!q.empty() && q.front() <= i - k) q.pop_front();
    while (!q.empty() && s[q.back()] <= s[i]) q.pop_back();
    if (q.empty()) q.pb(i, 1e18);
    else q.pb(i, f[q.back()] + s[i]);
    f[i] = min(q.getmin(), (i >= k ? f[i - k] : 0) + s[q.front()]);
    res = (res * 23 + f[i]) % mod;
  }
  return res;
}
#ifdef test
int main() {
  int n = 8, k = 3;
  int s[] = {3, 2, 9, 8, 7, 11, 3, 4};
  cout << solve(n, k, s);
  return 0;
}
#endif

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;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~