#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (int i = 0; i < v.size(); i++) os << v[i] << " ";
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& v) {
  for (typename set<T>::iterator it = v.begin(); it != v.end(); it++)
    os << *it << " ";
}
const double eps = 1e-9;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
int sgn(double a) { return a < -eps ? -1 : a < eps ? 0 : 1; }
int gi() {
  int w = 0;
  bool q = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') q = 0, c = getchar();
  while (c >= '0' && c <= '9') w = w * 10 + c - '0', c = getchar();
  return q ? w : -w;
}
int A[N], s[N], l[N], r[N];
const int mo = 1e9 + 7, inv2 = 500000004, inv6 = 166666668;
int a, b, c;
struct data {
  int f, g, h;
};
data calc(int a, int b, int c, long long n) {
  data tmp;
  if (!a) {
    tmp.f = tmp.g = tmp.h = 0;
    return tmp;
  }
  if (a >= c || b >= c) {
    tmp = calc(a % c, b % c, c, n);
    n %= mo;
    tmp.h = (tmp.h +
             n * (n + 1) % mo * (2 * n + 1) % mo * inv6 % mo * (a / c) % mo *
                 (a / c) % mo +
             (n + 1) * (b / c) % mo * (b / c) % mo +
             (long long)2 * (a / c) * tmp.g % mo +
             (long long)2 * (b / c) * tmp.f % mo +
             n * (n + 1) % mo * (a / c) % mo * (b / c)) %
            mo;
    tmp.f = (tmp.f + n * (n + 1) / 2 % mo * (a / c) + (n + 1) * (b / c)) % mo;
    tmp.g = (tmp.g + n * (n + 1) % mo * (2 * n + 1) % mo * inv6 % mo * (a / c) +
             n * (n + 1) / 2 % mo * (b / c)) %
            mo;
    return tmp;
  }
  long long m = ((long long)a * n + b) / c;
  data nxt = calc(c, c - b - 1, a, m - 1);
  n %= mo;
  m %= mo;
  tmp.f = ((n * m - nxt.f) % mo + mo) % mo;
  tmp.g =
      (long long)((n * (n + 1) % mo * m - nxt.f - nxt.h) % mo + mo) * inv2 % mo;
  tmp.h =
      ((m * (m + 1) % mo * n - (long long)2 * (nxt.g + nxt.f) % mo - tmp.f) %
           mo +
       mo) %
      mo;
  return tmp;
}
int main() {
  int n = gi(), k = gi();
  for (int i = (1); i <= (n); i++) {
    A[i] = gi();
  }
  int top = 0;
  for (int i = (1); i <= (n); i++) {
    while (top && A[s[top - 1]] <= A[i]) {
      top--;
    }
    if (top) {
      l[i] = s[top - 1] + 1;
    } else {
      l[i] = 1;
    }
    s[top++] = i;
  }
  top = 0;
  for (int i = (n); i >= (1); i--) {
    while (top && A[s[top - 1]] < A[i]) {
      top--;
    }
    if (top) {
      r[i] = s[top - 1] - 1;
    } else
      r[i] = n;
    s[top++] = i;
  }
  int ans = 0;
  for (int i = (1); i <= (n); i++) {
    int tmp = calc(1, r[i] - i, k - 1, i - l[i]).f -
              calc(1, 0, k - 1, i - l[i] - 1).f;
    if (tmp < 0) tmp += mo;
    ans += (long long)A[i] * tmp % mo;
    if (ans >= mo) ans -= mo;
  }
  cout << ans;
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

Given an array a of n integers and an integer k (2 ≤ k ≤ n), where each element of the array is denoted by a_i (0 ≤ i < n). Perform the operation z given below on a and print the value of z(a,k) modulo 10^{9}+7.
    
    
      
    function z(array a, integer k):  
        if length(a) < k:  
            return 0  
        else:  
            b = empty array  
            ans = 0  
            for i = 0 .. (length(a) - k):  
                temp = a[i]  
                for j = i .. (i + k - 1):  
                    temp = max(temp, a[j])  
                append temp to the end of b  
                ans = ans + temp  
            return ans + z(b, k)  
    

Input

The first line of input contains two integers n and k (2 ≤ k ≤ n ≤ 10^6) — the length of the initial array a and the parameter k.

The second line of input contains n integers a_0, a_1, …, a_{n - 1} (1 ≤ a_{i} ≤ 10^9) — the elements of the array a.

Output

Output the only integer, the value of z(a,k) modulo 10^9+7.

Examples

Input

3 2
9 1 10


Output

29


Input

5 3
5 8 7 1 9


Output

34

Note

In the first example: 

  * for a=(9,1,10), ans=19 and b=(9,10), 
  * for a=(9,10), ans=10 and b=(10), 
  * for a=(10), ans=0. 



So the returned value is 19+10+0=29.

In the second example: 

  * for a=(5,8,7,1,9), ans=25 and b=(8,8,9), 
  * for a=(8,8,9), ans=9 and b=(9), 
  * for a=(9), ans=0. 



So the returned value is 25+9+0=34.

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (int i = 0; i < v.size(); i++) os << v[i] << " ";
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& v) {
  for (typename set<T>::iterator it = v.begin(); it != v.end(); it++)
    os << *it << " ";
}
const double eps = 1e-9;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
int sgn(double a) { return a < -eps ? -1 : a < eps ? 0 : 1; }
int gi() {
  int w = 0;
  bool q = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') q = 0, c = getchar();
  while (c >= '0' && c <= '9') w = w * 10 + c - '0', c = getchar();
  return q ? w : -w;
}
int A[N], s[N], l[N], r[N];
const int mo = 1e9 + 7, inv2 = 500000004, inv6 = 166666668;
int a, b, c;
struct data {
  int f, g, h;
};
data calc(int a, int b, int c, long long n) {
  data tmp;
  if (!a) {
    tmp.f = tmp.g = tmp.h = 0;
    return tmp;
  }
  if (a >= c || b >= c) {
    tmp = calc(a % c, b % c, c, n);
    n %= mo;
    tmp.h = (tmp.h +
             n * (n + 1) % mo * (2 * n + 1) % mo * inv6 % mo * (a / c) % mo *
                 (a / c) % mo +
             (n + 1) * (b / c) % mo * (b / c) % mo +
             (long long)2 * (a / c) * tmp.g % mo +
             (long long)2 * (b / c) * tmp.f % mo +
             n * (n + 1) % mo * (a / c) % mo * (b / c)) %
            mo;
    tmp.f = (tmp.f + n * (n + 1) / 2 % mo * (a / c) + (n + 1) * (b / c)) % mo;
    tmp.g = (tmp.g + n * (n + 1) % mo * (2 * n + 1) % mo * inv6 % mo * (a / c) +
             n * (n + 1) / 2 % mo * (b / c)) %
            mo;
    return tmp;
  }
  long long m = ((long long)a * n + b) / c;
  data nxt = calc(c, c - b - 1, a, m - 1);
  n %= mo;
  m %= mo;
  tmp.f = ((n * m - nxt.f) % mo + mo) % mo;
  tmp.g =
      (long long)((n * (n + 1) % mo * m - nxt.f - nxt.h) % mo + mo) * inv2 % mo;
  tmp.h =
      ((m * (m + 1) % mo * n - (long long)2 * (nxt.g + nxt.f) % mo - tmp.f) %
           mo +
       mo) %
      mo;
  return tmp;
}
int main() {
  int n = gi(), k = gi();
  for (int i = (1); i <= (n); i++) {
    A[i] = gi();
  }
  int top = 0;
  for (int i = (1); i <= (n); i++) {
    while (top && A[s[top - 1]] <= A[i]) {
      top--;
    }
    if (top) {
      l[i] = s[top - 1] + 1;
    } else {
      l[i] = 1;
    }
    s[top++] = i;
  }
  top = 0;
  for (int i = (n); i >= (1); i--) {
    while (top && A[s[top - 1]] < A[i]) {
      top--;
    }
    if (top) {
      r[i] = s[top - 1] - 1;
    } else
      r[i] = n;
    s[top++] = i;
  }
  int ans = 0;
  for (int i = (1); i <= (n); i++) {
    int tmp = calc(1, r[i] - i, k - 1, i - l[i]).f -
              calc(1, 0, k - 1, i - l[i] - 1).f;
    if (tmp < 0) tmp += mo;
    ans += (long long)A[i] * tmp % mo;
    if (ans >= mo) ans -= mo;
  }
  cout << ans;
  return 0;
}

```