| Codeforces Round 446 (Div. 1) |
|---|
| Закончено |
Вам дана последовательность из 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
