Вам дан массив \(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)
Выходные данные
Выведите одно целое число — значение \(z(a,k)\) взятое по модулю \(10^9+7\).
Примечание
В первом примере:
- для \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
9 1 10
|
29
|
|
2
|
5 3
5 8 7 1 9
|
34
|