Вам дана последовательность из n целых чисел. Также у вас есть переменная res, которая изначально равна 0. Следующая операция выполняется k раз.
Выбирается индекс от 1 до n равновероятно случайным образом, назовем его x. К переменной res прибавляется произведение всех ai таких, что 1 ≤ i ≤ n, но i ≠ x. Затем из ax вычитается 1.
Найдите математическое ожидание величины res в конце процесса. Можно показать, что ожидаемое значение величины res может быть представлено как несократимая дробь 
. Вам необходимо найти значение 
.
Выходные данные
Выведите одно целое число — значение .
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
5 5
|
5
|
|
2
|
1 10
80
|
10
|
|
3
|
2 2
0 0
|
500000003
|
|
4
|
9 4
0 11 12 9 20 7 8 18 2
|
169316356
|