Перика начала играть на пианино. Оно у нее особенное - на нем есть N клавиш, и на каждой написано число a _i . В процессе игры Перика одновременно нажимает K клавиш, но так как пианино особенное, звук издаст только клавиша с наибольшим числом среди нажатых. Перика собирается нажать каждую из возможных комбинаций из K клавиш и хочет знать сумму чисел на тех клавишах, которые при этом издадут звуки.

Помогите Перике и ответьте на ее вопрос. Так как ответ может быть очень большим, выведите его по модулю 1 000 000 007.

Вам дан массив целых чисел длины N . Пусть s ₁ , s ₂ , ... , s _q - массив его непустых подпоследовательностей, отсортированный в лексикографическом порядке.

Подпоследовательностью массива называется массив, полученным путем вычеркивания нескольких (возможно, 0) элементов из изначального массива. Заметьте, что некоторые подпоследовательности могут быть одинаковыми, поэтому q = 2 ^N - 1 .

Массив A лексикографически меньше массива B , если A _i < B _i , где i - первая позиция, в которой массивы различаются, или если A - строгий префикс B .

Определим хеш массива s , состоящего из элементов v ₁ , v ₂ , ... , v _p , как: h ( s )  =  ( v ₁ · B ^{p - 1} + v ₂ · B ^{p - 2} + ... + v _{p - 1} · B + v _p ) mod M , где B и M - данные числа.

Посчитайте h ( s ₁ ) , h ( s ₂ ) , ... , h ( s _K ) для данного K .