E. Похоть
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана последовательность из n целых чисел. Также у вас есть переменная res, которая изначально равна 0. Следующая операция выполняется k раз.

Выбирается индекс от 1 до n равновероятно случайным образом, назовем его x. К переменной res прибавляется произведение всех ai таких, что 1 ≤ i ≤ n, но i ≠ x. Затем из ax вычитается 1.

Найдите математическое ожидание величины res в конце процесса. Можно показать, что ожидаемое значение величины res может быть представлено как несократимая дробь . Вам необходимо найти значение .

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

Первая строка содержит два целых числа n и k (1 ≤ n ≤ 5000, 1 ≤ k ≤ 109) — количество элементов и параметр k, описанный в условии.

Вторая строка содержит n целых чисел a1, a2, ..., an (0 ≤ ai ≤ 109).

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

Выведите одно целое число — значение .

Примеры
Входные данные
2 1
5 5
Выходные данные
5
Входные данные
1 10
80
Выходные данные
10
Входные данные
2 2
0 0
Выходные данные
500000003
Входные данные
9 4
0 11 12 9 20 7 8 18 2
Выходные данные
169316356