#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
bool cmax(T& a, const U& b) {
  return a < b ? a = b, 1 : 0;
}
template <class T, class U>
bool cmin(T& a, const U& b) {
  return b < a ? a = b, 1 : 0;
}
void _BG(const char* s) { cerr << s << endl; };
template <class T, class... TT>
void _BG(const char* s, T a, TT... b) {
  for (int c = 0; *s && (c || *s != ','); ++s) {
    cerr << *s;
    for (char x : "([{") c += *s == x;
    for (char x : ")]}") c -= *s == x;
  }
  cerr << " = " << a;
  if (sizeof...(b)) {
    cerr << ", ";
    ++s;
  }
  _BG(s, b...);
}
bool RD() { return 1; }
bool RD(char& a) { return scanf(" %c", &a) == 1; }
bool RD(char* a) { return scanf("%s", a) == 1; }
bool RD(double& a) { return scanf("%lf", &a) == 1; }
bool RD(int& a) { return scanf("%d", &a) == 1; }
bool RD(long long& a) { return scanf("%lld", &a) == 1; }
template <class T, class... TT>
bool RD(T& a, TT&... b) {
  return RD(a) && RD(b...);
}
void PT(const char& a) { putchar(a); }
void PT(char const* const& a) { fputs(a, stdout); }
void PT(const double& a) { printf("%.16f", a); }
void PT(const int& a) { printf("%d", a); }
void PT(const long long& a) { printf("%lld", a); }
template <char s = ' ', char e = '\n'>
void PL() {
  if (e) PT(e);
}
template <char s = ' ', char e = '\n', class T, class... TT>
void PL(const T& a, const TT&... b) {
  PT(a);
  if (sizeof...(b) && s) PT(s);
  PL<s, e>(b...);
}
const int N = 1123456, M = 1e9 + 7;
const int I2 = (M + 1) / 2;
int n, k, a[N], lt[N], rt[N], st[N];
long long f(long long w) {
  long long s = (w - 1) / (k - 1);
  if (s < 1) return 0;
  return (s * w % M + M - (k - 1) * (1 + s) % M * s % M * I2 % M) % M;
}
int main() {
  RD(n, k);
  for (int i(1); i < ((n) + 1); ++i) RD(a[i]);
  a[0] = a[n + 1] = M;
  st[0] = 0;
  int tp = 1;
  for (int i(1); i < ((n) + 1); ++i) {
    while (a[st[tp - 1]] <= a[i]) --tp;
    lt[i] = st[tp - 1];
    st[tp++] = i;
  }
  st[0] = n + 1;
  tp = 1;
  for (int i(((n) + 1) - 1); i >= (1); --i) {
    while (a[st[tp - 1]] < a[i]) --tp;
    rt[i] = st[tp - 1];
    st[tp++] = i;
  }
  long long ans = 0;
  for (int i(1); i < ((n) + 1); ++i) {
    long long x = i - lt[i] - 1, y = rt[i] - i - 1;
    ans += (f(x + y + 1) + M - f(x) + M - f(y)) * a[i] % M;
  }
  PL(ans % M);
}

### Prompt

Please create a solution in CPP 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;
template <class T, class U>
bool cmax(T& a, const U& b) {
  return a < b ? a = b, 1 : 0;
}
template <class T, class U>
bool cmin(T& a, const U& b) {
  return b < a ? a = b, 1 : 0;
}
void _BG(const char* s) { cerr << s << endl; };
template <class T, class... TT>
void _BG(const char* s, T a, TT... b) {
  for (int c = 0; *s && (c || *s != ','); ++s) {
    cerr << *s;
    for (char x : "([{") c += *s == x;
    for (char x : ")]}") c -= *s == x;
  }
  cerr << " = " << a;
  if (sizeof...(b)) {
    cerr << ", ";
    ++s;
  }
  _BG(s, b...);
}
bool RD() { return 1; }
bool RD(char& a) { return scanf(" %c", &a) == 1; }
bool RD(char* a) { return scanf("%s", a) == 1; }
bool RD(double& a) { return scanf("%lf", &a) == 1; }
bool RD(int& a) { return scanf("%d", &a) == 1; }
bool RD(long long& a) { return scanf("%lld", &a) == 1; }
template <class T, class... TT>
bool RD(T& a, TT&... b) {
  return RD(a) && RD(b...);
}
void PT(const char& a) { putchar(a); }
void PT(char const* const& a) { fputs(a, stdout); }
void PT(const double& a) { printf("%.16f", a); }
void PT(const int& a) { printf("%d", a); }
void PT(const long long& a) { printf("%lld", a); }
template <char s = ' ', char e = '\n'>
void PL() {
  if (e) PT(e);
}
template <char s = ' ', char e = '\n', class T, class... TT>
void PL(const T& a, const TT&... b) {
  PT(a);
  if (sizeof...(b) && s) PT(s);
  PL<s, e>(b...);
}
const int N = 1123456, M = 1e9 + 7;
const int I2 = (M + 1) / 2;
int n, k, a[N], lt[N], rt[N], st[N];
long long f(long long w) {
  long long s = (w - 1) / (k - 1);
  if (s < 1) return 0;
  return (s * w % M + M - (k - 1) * (1 + s) % M * s % M * I2 % M) % M;
}
int main() {
  RD(n, k);
  for (int i(1); i < ((n) + 1); ++i) RD(a[i]);
  a[0] = a[n + 1] = M;
  st[0] = 0;
  int tp = 1;
  for (int i(1); i < ((n) + 1); ++i) {
    while (a[st[tp - 1]] <= a[i]) --tp;
    lt[i] = st[tp - 1];
    st[tp++] = i;
  }
  st[0] = n + 1;
  tp = 1;
  for (int i(((n) + 1) - 1); i >= (1); --i) {
    while (a[st[tp - 1]] < a[i]) --tp;
    rt[i] = st[tp - 1];
    st[tp++] = i;
  }
  long long ans = 0;
  for (int i(1); i < ((n) + 1); ++i) {
    long long x = i - lt[i] - 1, y = rt[i] - i - 1;
    ans += (f(x + y + 1) + M - f(x) + M - f(y)) * a[i] % M;
  }
  PL(ans % M);
}

```