#include <bits/stdc++.h>
using namespace std;
namespace io {
const int L = (1 << 21) | 1;
char ibuf[L], *iS, *iT, ch;
inline char gc() {
  if (iS == iT) {
    iT = (iS = ibuf) + fread(ibuf, 1, L, stdin);
    if (iS == iT) return EOF;
  }
  return *iS++;
}
inline void gi(int &ret) {
  while (ch = gc(), !isdigit(ch))
    ;
  ret = ch - '0';
  while (ch = gc(), isdigit(ch)) ret = ret * 10 + ch - '0';
}
}  // namespace io
using io::gi;
const int maxn = 1000005;
const int mod = 1000000000 + 7;
struct node_t {
  int c, w;
};
int n, k, Ans;
int seq[maxn], sum[maxn], mx[maxn];
int que[maxn], st = 1, ed;
vector<node_t> vec[maxn];
int main() {
  gi(n), gi(k), --k;
  for (int i = 1; i <= n; i++) gi(seq[i]);
  for (int i = n; i >= 1; i--) {
    while (st <= ed && que[st] > i + k - 1) ++st;
    while (st <= ed && seq[que[ed]] <= seq[i]) --ed;
    que[++ed] = i, mx[i] = seq[que[st]];
  }
  for (int i = n - k + 1; i >= 1; i--) {
    int id = (i + 1) % k, _c = 0, _s = sum[id];
    for (int j = vec[id].size() - 1; j >= 0; j--)
      if (vec[id][j].w < seq[i])
        _s = (_s - 1ll * vec[id][j].w * vec[id][j].c % mod + mod) % mod,
        _c += vec[id][j].c;
      else
        break;
    Ans = (Ans + _s + 1ll * seq[i] * _c) % mod;
    id = i % k, _c = 0;
    for (int j = vec[id].size() - 1; j >= 0; j--)
      if (vec[id][j].w < mx[i]) {
        _c += vec[id][j].c;
        sum[id] =
            (sum[id] - 1ll * vec[id][j].w * vec[id][j].c % mod + mod) % mod;
        vec[id].pop_back();
      } else
        break;
    sum[id] = (sum[id] + 1ll * (_c + 1) * mx[i]) % mod;
    vec[id].push_back((node_t){_c + 1, mx[i]});
  }
  printf("%d\n", Ans);
  return 0;
}

### Prompt

Develop a solution in cpp 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;
namespace io {
const int L = (1 << 21) | 1;
char ibuf[L], *iS, *iT, ch;
inline char gc() {
  if (iS == iT) {
    iT = (iS = ibuf) + fread(ibuf, 1, L, stdin);
    if (iS == iT) return EOF;
  }
  return *iS++;
}
inline void gi(int &ret) {
  while (ch = gc(), !isdigit(ch))
    ;
  ret = ch - '0';
  while (ch = gc(), isdigit(ch)) ret = ret * 10 + ch - '0';
}
}  // namespace io
using io::gi;
const int maxn = 1000005;
const int mod = 1000000000 + 7;
struct node_t {
  int c, w;
};
int n, k, Ans;
int seq[maxn], sum[maxn], mx[maxn];
int que[maxn], st = 1, ed;
vector<node_t> vec[maxn];
int main() {
  gi(n), gi(k), --k;
  for (int i = 1; i <= n; i++) gi(seq[i]);
  for (int i = n; i >= 1; i--) {
    while (st <= ed && que[st] > i + k - 1) ++st;
    while (st <= ed && seq[que[ed]] <= seq[i]) --ed;
    que[++ed] = i, mx[i] = seq[que[st]];
  }
  for (int i = n - k + 1; i >= 1; i--) {
    int id = (i + 1) % k, _c = 0, _s = sum[id];
    for (int j = vec[id].size() - 1; j >= 0; j--)
      if (vec[id][j].w < seq[i])
        _s = (_s - 1ll * vec[id][j].w * vec[id][j].c % mod + mod) % mod,
        _c += vec[id][j].c;
      else
        break;
    Ans = (Ans + _s + 1ll * seq[i] * _c) % mod;
    id = i % k, _c = 0;
    for (int j = vec[id].size() - 1; j >= 0; j--)
      if (vec[id][j].w < mx[i]) {
        _c += vec[id][j].c;
        sum[id] =
            (sum[id] - 1ll * vec[id][j].w * vec[id][j].c % mod + mod) % mod;
        vec[id].pop_back();
      } else
        break;
    sum[id] = (sum[id] + 1ll * (_c + 1) * mx[i]) % mod;
    vec[id].push_back((node_t){_c + 1, mx[i]});
  }
  printf("%d\n", Ans);
  return 0;
}

```