#include <bits/stdc++.h>
using namespace std;
inline int read() {
  char ch = getchar();
  int ret = 0;
  while (ch < '0' || ch > '9') ch = getchar();
  for (; ch >= '0' && ch <= '9'; ch = getchar()) ret = ret * 10 + ch - '0';
  return ret;
}
const int INF = 1 << 30;
const int MOD = 1e9 + 7;
const int maxn = 1000000 + 10;
struct Node {
  Node *lc, *rc;
  int M;
  Node() {
    lc = rc = NULL;
    M = 0;
  }
  inline void up() { M = max(lc->M, rc->M); }
} * root;
int a[maxn];
void build(Node*& p, int l, int r) {
  p = new Node();
  if (l == r) {
    p->M = a[l];
    return;
  }
  build(p->lc, l, ((l + r) >> 1));
  build(p->rc, ((l + r) >> 1) + 1, r);
  p->up();
}
int query(Node* p, int l, int r, int L, int R) {
  if (L <= l && r <= R) return p->M;
  int ret = 0;
  if (L <= ((l + r) >> 1))
    ret = max(ret, query(p->lc, l, ((l + r) >> 1), L, R));
  if (((l + r) >> 1) < R)
    ret = max(ret, query(p->rc, ((l + r) >> 1) + 1, r, L, R));
  return ret;
}
int st[maxn], sz[maxn], Pos[maxn], top;
long long sum[maxn];
inline int find(int val) {
  int l = 1, r = top, ans = top + 1, mid;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (st[mid] <= val)
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  return ans;
}
int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) a[i] = read();
  build(root, 1, n);
  long long Ans = 0;
  Ans %= MOD;
  for (int i = 0; i <= k - 2; ++i) {
    long long ans = 0;
    top = 0;
    for (int pos = i + k, j = 1; pos <= n; pos += (k - 1), ++j) {
      int t = query(root, 1, n, pos - (k - 1), pos - 1);
      int tsz = 1;
      while (top && st[top] < t) {
        tsz += sz[top];
        ans -= 1ll * sz[top] * st[top];
        Pos[top] = sum[top] = st[top] = sz[top] = 0;
        --top;
      }
      ++top;
      sum[top] = (sum[top - 1] + 1ll * t * tsz) % MOD;
      st[top] = t;
      sz[top] = tsz;
      Pos[top] = j;
      int p = find(a[pos]);
      if (p <= top)
        Ans += sum[p - 1] + 1ll * (j - (Pos[p - 1] + 1) + 1) * a[pos];
      else
        Ans += sum[top];
      Ans %= MOD;
    }
    Ans %= MOD;
    for (; top; --top) Pos[top] = sum[top] = st[top] = sz[top] = 0;
  }
  cout << (Ans % MOD + MOD) % MOD << endl;
  return 0;
}

### Prompt

In cpp, your task is to solve the following problem:

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;
inline int read() {
  char ch = getchar();
  int ret = 0;
  while (ch < '0' || ch > '9') ch = getchar();
  for (; ch >= '0' && ch <= '9'; ch = getchar()) ret = ret * 10 + ch - '0';
  return ret;
}
const int INF = 1 << 30;
const int MOD = 1e9 + 7;
const int maxn = 1000000 + 10;
struct Node {
  Node *lc, *rc;
  int M;
  Node() {
    lc = rc = NULL;
    M = 0;
  }
  inline void up() { M = max(lc->M, rc->M); }
} * root;
int a[maxn];
void build(Node*& p, int l, int r) {
  p = new Node();
  if (l == r) {
    p->M = a[l];
    return;
  }
  build(p->lc, l, ((l + r) >> 1));
  build(p->rc, ((l + r) >> 1) + 1, r);
  p->up();
}
int query(Node* p, int l, int r, int L, int R) {
  if (L <= l && r <= R) return p->M;
  int ret = 0;
  if (L <= ((l + r) >> 1))
    ret = max(ret, query(p->lc, l, ((l + r) >> 1), L, R));
  if (((l + r) >> 1) < R)
    ret = max(ret, query(p->rc, ((l + r) >> 1) + 1, r, L, R));
  return ret;
}
int st[maxn], sz[maxn], Pos[maxn], top;
long long sum[maxn];
inline int find(int val) {
  int l = 1, r = top, ans = top + 1, mid;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (st[mid] <= val)
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  return ans;
}
int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) a[i] = read();
  build(root, 1, n);
  long long Ans = 0;
  Ans %= MOD;
  for (int i = 0; i <= k - 2; ++i) {
    long long ans = 0;
    top = 0;
    for (int pos = i + k, j = 1; pos <= n; pos += (k - 1), ++j) {
      int t = query(root, 1, n, pos - (k - 1), pos - 1);
      int tsz = 1;
      while (top && st[top] < t) {
        tsz += sz[top];
        ans -= 1ll * sz[top] * st[top];
        Pos[top] = sum[top] = st[top] = sz[top] = 0;
        --top;
      }
      ++top;
      sum[top] = (sum[top - 1] + 1ll * t * tsz) % MOD;
      st[top] = t;
      sz[top] = tsz;
      Pos[top] = j;
      int p = find(a[pos]);
      if (p <= top)
        Ans += sum[p - 1] + 1ll * (j - (Pos[p - 1] + 1) + 1) * a[pos];
      else
        Ans += sum[top];
      Ans %= MOD;
    }
    Ans %= MOD;
    for (; top; --top) Pos[top] = sum[top] = st[top] = sz[top] = 0;
  }
  cout << (Ans % MOD + MOD) % MOD << endl;
  return 0;
}

```