#include <bits/stdc++.h>
using namespace std;
const double PI = 2 * acos(0.0);
template <typename T>
struct edge {
  int from, to;
  T w;
  edge(int from, int to, T w) : from(from), to(to), w(w) {}
  edge() {}
};
template <class T, class C>
void show(C a) {
  for (T x : a) cout << x << " ";
  cout << endl;
}
const long long M = 1e9 + 7;
const int N = 1e6 + 9;
long long n, k;
inline long long get(long long l, long long r) {
  l = max(l, (1LL));
  if (l > r) return 0;
  --l;
  long long a = (r - l) % M;
  long long b = (r * (r + 1) - l * (l + 1)) / 2;
  b %= M;
  b = (b * (k - 1));
  return (a + b) % M;
}
inline long long get(long long l, long long r, long long d) {
  l = max(l, (1LL));
  if (l > r) return 0;
  --l;
  long long a = (d * (r - l)) % M;
  long long b = (r * (r + 1) - l * (l + 1)) / 2;
  b %= M;
  b = (b * (k - 1));
  return (b - a + M) % M;
}
int parent[N];
int sz[N];
int lf[N], rf[N];
bool is[N];
inline bool is_set(int v) { return v >= 0 && v < n && is[v]; }
inline void make_set(int v) {
  is[v] = true;
  parent[v] = v;
  sz[v] = 1;
  lf[v] = rf[v] = v;
}
int find_set(int v) {
  if (parent[v] == v) return v;
  return parent[v] = find_set(parent[v]);
}
inline void union_sets(int u, int v) {
  u = find_set(u);
  v = find_set(v);
  if (u == v) return;
  if (sz[u] < sz[v]) swap(v, u);
  lf[u] = min(lf[u], (lf[v]));
  rf[u] = max(rf[u], (rf[v]));
  sz[u] += sz[v];
  parent[v] = u;
}
vector<long long> a;
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  a.resize(n);
  vector<pair<long long, long long> > kek(n);
  for (int i = 0; i < int(n); ++i) {
    cin >> a[i];
    kek[i] = make_pair(a[i], i);
  }
  sort(kek.begin(), kek.end());
  long long all = 0;
  for (auto x : kek) {
    make_set(x.second);
    if (is_set(x.second - 1)) union_sets(x.second, x.second - 1);
    if (is_set(x.second + 1)) union_sets(x.second, x.second + 1);
    int ind = x.second;
    int v = find_set(ind);
    int l = lf[v];
    int r = rf[v];
    int d1 = abs(ind - l) + 1, d2 = abs(r - ind) + 1;
    if (d1 > d2) swap(d1, d2);
    int f0 = 1;
    int f1 = (d1 - 1) / (k - 1);
    int f2 = (d2 - 1) / (k - 1);
    int f3 = (d2 + d1 - 2) / (k - 1);
    long long ans = 0;
    ans = ((ans) + (get(f0, f3)) >= M ? (ans) + (get(f0, f3)) - M
                                      : (ans) + (get(f0, f3)));
    ans = ((ans) - (get(f1 + 1, f3, d1 - 1)) < 0
               ? (ans) - (get(f1 + 1, f3, d1 - 1)) + M
               : (ans) - (get(f1 + 1, f3, d1 - 1)));
    ans = ((ans) - (get(f2 + 1, f3, d2 - 1)) < 0
               ? (ans) - (get(f2 + 1, f3, d2 - 1)) + M
               : (ans) - (get(f2 + 1, f3, d2 - 1)));
    ans = (ans * x.first) % M;
    all = ((all) + (ans) >= M ? (all) + (ans)-M : (all) + (ans));
  }
  cout << all;
}

### Prompt

Create a solution in Cpp for 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;
const double PI = 2 * acos(0.0);
template <typename T>
struct edge {
  int from, to;
  T w;
  edge(int from, int to, T w) : from(from), to(to), w(w) {}
  edge() {}
};
template <class T, class C>
void show(C a) {
  for (T x : a) cout << x << " ";
  cout << endl;
}
const long long M = 1e9 + 7;
const int N = 1e6 + 9;
long long n, k;
inline long long get(long long l, long long r) {
  l = max(l, (1LL));
  if (l > r) return 0;
  --l;
  long long a = (r - l) % M;
  long long b = (r * (r + 1) - l * (l + 1)) / 2;
  b %= M;
  b = (b * (k - 1));
  return (a + b) % M;
}
inline long long get(long long l, long long r, long long d) {
  l = max(l, (1LL));
  if (l > r) return 0;
  --l;
  long long a = (d * (r - l)) % M;
  long long b = (r * (r + 1) - l * (l + 1)) / 2;
  b %= M;
  b = (b * (k - 1));
  return (b - a + M) % M;
}
int parent[N];
int sz[N];
int lf[N], rf[N];
bool is[N];
inline bool is_set(int v) { return v >= 0 && v < n && is[v]; }
inline void make_set(int v) {
  is[v] = true;
  parent[v] = v;
  sz[v] = 1;
  lf[v] = rf[v] = v;
}
int find_set(int v) {
  if (parent[v] == v) return v;
  return parent[v] = find_set(parent[v]);
}
inline void union_sets(int u, int v) {
  u = find_set(u);
  v = find_set(v);
  if (u == v) return;
  if (sz[u] < sz[v]) swap(v, u);
  lf[u] = min(lf[u], (lf[v]));
  rf[u] = max(rf[u], (rf[v]));
  sz[u] += sz[v];
  parent[v] = u;
}
vector<long long> a;
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  a.resize(n);
  vector<pair<long long, long long> > kek(n);
  for (int i = 0; i < int(n); ++i) {
    cin >> a[i];
    kek[i] = make_pair(a[i], i);
  }
  sort(kek.begin(), kek.end());
  long long all = 0;
  for (auto x : kek) {
    make_set(x.second);
    if (is_set(x.second - 1)) union_sets(x.second, x.second - 1);
    if (is_set(x.second + 1)) union_sets(x.second, x.second + 1);
    int ind = x.second;
    int v = find_set(ind);
    int l = lf[v];
    int r = rf[v];
    int d1 = abs(ind - l) + 1, d2 = abs(r - ind) + 1;
    if (d1 > d2) swap(d1, d2);
    int f0 = 1;
    int f1 = (d1 - 1) / (k - 1);
    int f2 = (d2 - 1) / (k - 1);
    int f3 = (d2 + d1 - 2) / (k - 1);
    long long ans = 0;
    ans = ((ans) + (get(f0, f3)) >= M ? (ans) + (get(f0, f3)) - M
                                      : (ans) + (get(f0, f3)));
    ans = ((ans) - (get(f1 + 1, f3, d1 - 1)) < 0
               ? (ans) - (get(f1 + 1, f3, d1 - 1)) + M
               : (ans) - (get(f1 + 1, f3, d1 - 1)));
    ans = ((ans) - (get(f2 + 1, f3, d2 - 1)) < 0
               ? (ans) - (get(f2 + 1, f3, d2 - 1)) + M
               : (ans) - (get(f2 + 1, f3, d2 - 1)));
    ans = (ans * x.first) % M;
    all = ((all) + (ans) >= M ? (all) + (ans)-M : (all) + (ans));
  }
  cout << all;
}

```