#include <bits/stdc++.h>
using namespace std;
string to_string(const string& str) { return str; }
template <typename T>
string to_string(const set<T>& mys) {
  if (mys.empty()) return "{}";
  string ret = "{";
  for (auto el : mys) ret += to_string(el) + ", ";
  ret.pop_back(), ret.pop_back();
  ret += "}";
  return ret;
}
template <typename T>
string to_string(const pair<T, T>& pr) {
  return "(" + to_string(pr.first) + "," + to_string(pr.second) + ")";
}
template <typename T>
string to_string(const vector<T>& vc, int w) {
  if (vc.empty()) return "";
  if (w + 1 == vc.size()) return to_string(vc[w]);
  return to_string(vc[w]) + "," + to_string(vc, w + 1);
}
template <typename T>
string to_string(const vector<T>& vc) {
  return "{" + to_string(vc, 0) + "}";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
class DebugStream {
} LOG;
template <typename T>
DebugStream& operator<<(DebugStream& s, const T&) {
  return s;
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 335, lg = 20,
          bs = 29;
long long arr[maxN], cnt[maxN], ans;
int T[maxN << 1], n, k;
inline int gb(int a, int b) {
  if (b == -1 || (a != -1 && arr[a] > arr[b])) return a;
  return b;
}
int qry(int l, int r) {
  int ret = -1;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) ret = gb(ret, T[l++]);
    if (r & 1) ret = gb(ret, T[--r]);
  }
  return ret;
}
long long getCnt(long long a, long long b) {
  if (b < a) swap(a, b);
  long long ret = 0;
  for (int i = 1; i <= a + 1; i++) ret = (ret + cnt[i + b] - cnt[i - 1]) % MOD;
  return ret;
}
void solve(int le, int ri) {
  int w = qry(le, ri);
  long long cn = getCnt(w - le, ri - w - 1);
  ans = (ans + arr[w] * cn) % MOD;
  if (le < w) solve(le, w);
  if (w + 1 < ri) solve(w + 1, ri);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> arr[i];
  for (int u = k; u <= n; u += k - 1) cnt[u]++;
  for (int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
  iota(T + n, T + n * 2, 0);
  for (int i = n - 1; i > 0; i--) T[i] = gb(T[i << 1], T[i << 1 | 1]);
  solve(0, n);
  cout << ans << '\n';
}

### Prompt

Generate a CPP solution to 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;
string to_string(const string& str) { return str; }
template <typename T>
string to_string(const set<T>& mys) {
  if (mys.empty()) return "{}";
  string ret = "{";
  for (auto el : mys) ret += to_string(el) + ", ";
  ret.pop_back(), ret.pop_back();
  ret += "}";
  return ret;
}
template <typename T>
string to_string(const pair<T, T>& pr) {
  return "(" + to_string(pr.first) + "," + to_string(pr.second) + ")";
}
template <typename T>
string to_string(const vector<T>& vc, int w) {
  if (vc.empty()) return "";
  if (w + 1 == vc.size()) return to_string(vc[w]);
  return to_string(vc[w]) + "," + to_string(vc, w + 1);
}
template <typename T>
string to_string(const vector<T>& vc) {
  return "{" + to_string(vc, 0) + "}";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
class DebugStream {
} LOG;
template <typename T>
DebugStream& operator<<(DebugStream& s, const T&) {
  return s;
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 335, lg = 20,
          bs = 29;
long long arr[maxN], cnt[maxN], ans;
int T[maxN << 1], n, k;
inline int gb(int a, int b) {
  if (b == -1 || (a != -1 && arr[a] > arr[b])) return a;
  return b;
}
int qry(int l, int r) {
  int ret = -1;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) ret = gb(ret, T[l++]);
    if (r & 1) ret = gb(ret, T[--r]);
  }
  return ret;
}
long long getCnt(long long a, long long b) {
  if (b < a) swap(a, b);
  long long ret = 0;
  for (int i = 1; i <= a + 1; i++) ret = (ret + cnt[i + b] - cnt[i - 1]) % MOD;
  return ret;
}
void solve(int le, int ri) {
  int w = qry(le, ri);
  long long cn = getCnt(w - le, ri - w - 1);
  ans = (ans + arr[w] * cn) % MOD;
  if (le < w) solve(le, w);
  if (w + 1 < ri) solve(w + 1, ri);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> arr[i];
  for (int u = k; u <= n; u += k - 1) cnt[u]++;
  for (int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
  iota(T + n, T + n * 2, 0);
  for (int i = n - 1; i > 0; i--) T[i] = gb(T[i << 1], T[i << 1 | 1]);
  solve(0, n);
  cout << ans << '\n';
}

```