F. Максимальное упрощение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел и целое число $$$k$$$ ($$$2 \le k \le n$$$), где элементы массива обозначаются как $$$a_i$$$ ($$$0 \le i < n$$$). Выполните операцию $$$z$$$ определённую ниже над $$$a$$$ и выведите значение $$$z(a,k)$$$ по модулю $$$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)
Входные данные

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le k \le n \le 10^6$$$) — длина исходного массива $$$a$$$ и параметр $$$k$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_0, a_1, \ldots, a_{n - 1}$$$ ($$$1 \le a_{i} \le 10^9$$$) — элементы массива $$$a$$$.

Выходные данные

Выведите одно целое число — значение $$$z(a,k)$$$ взятое по модулю $$$10^9+7$$$.

Примеры
Входные данные
3 2
9 1 10
Выходные данные
29
Входные данные
5 3
5 8 7 1 9
Выходные данные
34
Примечание

В первом примере:

  • для $$$a=(9,1,10)$$$, $$$ans=19$$$ и $$$b=(9,10)$$$,
  • для $$$a=(9,10)$$$, $$$ans=10$$$ и $$$b=(10)$$$,
  • для $$$a=(10)$$$, $$$ans=0$$$.

Значит, ответ равен $$$19+10+0=29$$$.

Во втором примере:

  • для $$$a=(5,8,7,1,9)$$$, $$$ans=25$$$ и $$$b=(8,8,9)$$$,
  • для $$$a=(8,8,9)$$$, $$$ans=9$$$ и $$$b=(9)$$$,
  • для $$$a=(9)$$$, $$$ans=0$$$.

Значит, ответ равен $$$25+9+0=34$$$.