#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T>
bool cmn(T& a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool cmx(T& a, T b) {
  return b > a ? a = b, true : false;
}
const int mod = 1e9 + 7, N = 1e6 + 10;
vector<pair<int, int> > s[N];
vector<int> f(vector<int> a, int k) {
  int n = (int)(a).size();
  stack<pair<int, int> > head;
  stack<int> tail;
  vector<int> res(n - k + 1);
  for (int i = 0; i < k; i++) {
    int x = ((int)(head).size() ? head.top().first : 0);
    head.push(make_pair(max(x, a[i]), i));
  }
  res[0] = head.top().first;
  for (int i = k; i < n; i++) {
    if (tail.empty()) {
      tail.push(a[head.top().second]);
      head.pop();
      while ((int)(head).size()) {
        tail.push(max(tail.top(), a[head.top().second]));
        head.pop();
      }
    }
    tail.pop();
    int x = ((int)(head).size() ? head.top().first : 0);
    head.push(make_pair(max(x, a[i]), i));
    res[i - k + 1] = head.top().first;
    if ((int)(tail).size()) cmx(res[i - k + 1], tail.top());
  }
  return res;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(n), sm(k - 1);
  for (int& i : a) cin >> i;
  auto b = f(a, k - 1);
  int ans = 0;
  for (int i = n - 1; i >= 0; i--) {
    int p = (i + 1) % (k - 1);
    if (i + k - 1 < n) {
      int x = a[i], S = 0;
      while ((int)(s[p]).size() && s[p].back().first <= x) {
        S += s[p].back().second;
        sm[p] -= 1ll * s[p].back().first * s[p].back().second % mod;
        if (sm[p] < 0) sm[p] += mod;
        s[p].pop_back();
      }
      sm[p] += 1ll * x * S % mod;
      if (sm[p] >= mod) sm[p] -= mod;
      s[p].push_back(make_pair(x, S));
      ans += sm[p];
      if (ans >= mod) ans -= mod;
    }
    if (i - k + 2 < 0) continue;
    int x = b[i - k + 2], S = 1;
    while ((int)(s[p]).size() && s[p].back().first <= x) {
      S += s[p].back().second;
      sm[p] -= 1ll * s[p].back().first * s[p].back().second % mod;
      if (sm[p] < 0) sm[p] += mod;
      s[p].pop_back();
    }
    sm[p] += 1ll * x * S % mod;
    if (sm[p] >= mod) sm[p] -= mod;
    s[p].push_back(make_pair(x, S));
  }
  cout << ans;
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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>
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T>
bool cmn(T& a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool cmx(T& a, T b) {
  return b > a ? a = b, true : false;
}
const int mod = 1e9 + 7, N = 1e6 + 10;
vector<pair<int, int> > s[N];
vector<int> f(vector<int> a, int k) {
  int n = (int)(a).size();
  stack<pair<int, int> > head;
  stack<int> tail;
  vector<int> res(n - k + 1);
  for (int i = 0; i < k; i++) {
    int x = ((int)(head).size() ? head.top().first : 0);
    head.push(make_pair(max(x, a[i]), i));
  }
  res[0] = head.top().first;
  for (int i = k; i < n; i++) {
    if (tail.empty()) {
      tail.push(a[head.top().second]);
      head.pop();
      while ((int)(head).size()) {
        tail.push(max(tail.top(), a[head.top().second]));
        head.pop();
      }
    }
    tail.pop();
    int x = ((int)(head).size() ? head.top().first : 0);
    head.push(make_pair(max(x, a[i]), i));
    res[i - k + 1] = head.top().first;
    if ((int)(tail).size()) cmx(res[i - k + 1], tail.top());
  }
  return res;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(n), sm(k - 1);
  for (int& i : a) cin >> i;
  auto b = f(a, k - 1);
  int ans = 0;
  for (int i = n - 1; i >= 0; i--) {
    int p = (i + 1) % (k - 1);
    if (i + k - 1 < n) {
      int x = a[i], S = 0;
      while ((int)(s[p]).size() && s[p].back().first <= x) {
        S += s[p].back().second;
        sm[p] -= 1ll * s[p].back().first * s[p].back().second % mod;
        if (sm[p] < 0) sm[p] += mod;
        s[p].pop_back();
      }
      sm[p] += 1ll * x * S % mod;
      if (sm[p] >= mod) sm[p] -= mod;
      s[p].push_back(make_pair(x, S));
      ans += sm[p];
      if (ans >= mod) ans -= mod;
    }
    if (i - k + 2 < 0) continue;
    int x = b[i - k + 2], S = 1;
    while ((int)(s[p]).size() && s[p].back().first <= x) {
      S += s[p].back().second;
      sm[p] -= 1ll * s[p].back().first * s[p].back().second % mod;
      if (sm[p] < 0) sm[p] += mod;
      s[p].pop_back();
    }
    sm[p] += 1ll * x * S % mod;
    if (sm[p] >= mod) sm[p] -= mod;
    s[p].push_back(make_pair(x, S));
  }
  cout << ans;
  return 0;
}

```