Задача №113579. Пианистка Перика
Перика начала играть на пианино. Оно у нее особенное - на нем есть N клавиш, и на каждой написано число a i . В процессе игры Перика одновременно нажимает K клавиш, но так как пианино особенное, звук издаст только клавиша с наибольшим числом среди нажатых. Перика собирается нажать каждую из возможных комбинаций из K клавиш и хочет знать сумму чисел на тех клавишах, которые при этом издадут звуки.
Помогите Перике и ответьте на ее вопрос. Так как ответ может быть очень большим, выведите его по модулю 1 000 000 007.
В первой строке содержатся два целых числа N и K ( 1 ≤ N ≤ 100000 , 1 ≤ K ≤ 50 ). Во второй строке содержатся N целых чисел a i ( 0 ≤ a i ≤ 10 9 ) - числа на клавишах пианино.
В единственной строке выведите одно целое число - ответ на вопрос Перики по модулю 1000000007.
Решения, работающие при 1 ≤ N ≤ 1000 , будут оцениваться в 40 баллов.
5 3 2 4 2 3 4
39
5 1 1 0 1 1 1
4
5 2 3 3 4 0 0
31