#include<bits/stdc++.h>
#include"peru.h"
constexpr int mod = 1e9 + 7;
constexpr int maxn = 2.5e6 + 10;
int f[maxn], s[maxn];
struct que {
   // top2 >= top1
   int stk1[maxn], val1[maxn], mn1[maxn], top1;
   int stk2[maxn], val2[maxn], mn2[maxn], top2;
   inline que() {
      top1 = top2 = 0;
      mn1[0] = mn2[0] = 1e9;
   }
   inline void update() {
      if (top1 && top2) return ;
      if (top1 + top2 == 0) return ;
      if (top1 + top2 == 1) {
         int x = top1 ? stk1[top1] : stk2[top2];
         top1 = 0, top2 = 1, stk2[1] = x;
         val2[1] = mn2[1] = 1e9;
         return ;
      }
      if (! top1) {
         top1 = top2 / 2, top2 -= top1;
         for (int i = 1; i <= top1; i++) {
            stk1[top1 - i + 1] = stk2[i];
         }
         for (int i = 1; i <= top2; i++) {
            stk2[i] = stk2[i + top1];
         }
      } else {
         top2 = (top1 + 1) / 2, top1 -= top2;
         for (int i = 1; i <= top2; i++) {
            stk2[top2 - i + 1] = stk1[i];
         }
         for (int i = 1; i <= top1; i++) {
            stk1[i] = stk1[i + top2];
         }
      }
      val1[top1] = 1e9;
      for (int i = 1, x, y; i < top1; i++) {
         x = stk1[i], y = stk1[i + 1];
         val1[i] = s[x] + f[y];
      }
      val2[1] = s[stk2[1]] + f[stk1[1]];
      for (int i = 2, x, y; i <= top2; i++) {
         x = stk2[i], y = stk2[i - 1];
         val2[i] = s[x] + f[y];
      }
      for (int i = 1; i <= top1; i++) {
         mn1[i] = std::min(val1[i], mn1[i - 1]);
      }
      for (int i = 1; i <= top2; i++) {
         mn2[i] = std::min(val2[i], mn2[i - 1]);
      }
   }
   inline void push_back(int x) {
      top2++;
      stk2[top2] = x, val2[top2] = top2 > 1 ? (s[x] + f[stk2[top2 - 1]]) : 1e9;
      mn2[top2] = std::min(val2[top2], mn2[top2 - 1]);
      update();
   }
   inline void pop_back() {
      top2--;
      update();
   }
   inline void pop_front() {
      if (top1) {
         top1--;
         val1[top1] = 1e9, mn1[top1] = std::min(val1[top1], top1 ? mn1[top1 - 1] : (int)1e9);
      } else {
         top2--;
      }
      update();
   }
   inline bool empty() {
      return top2 == 0;
   }
   inline int front() {
      return top1 ? stk1[top1] : stk2[1];
   }
   inline int back() {
      return stk2[top2];
   }
   inline int query() {
      return std::min(mn1[top1], mn2[top2]);
   }
} Q;
int solve(int n, int k, int* s_){
   int ans = 0;
   for (int i = 0; i < n; i++) {
      s[i] = s_[i];
      if (! Q.empty() && i - Q.front() >= k) Q.pop_front();
      while (! Q.empty() && s[i] > s[Q.back()]) Q.pop_back();
      Q.push_back(i);
      f[i] = std::min(Q.query(), s[Q.front()] + (i - k >= 0 ? f[i - k] : 0));
      ans = (23ll * ans + f[i]) % mod;
   }
   return ans;
}