В классе есть \(n\) детей, \(m\) пар среди них — друзья. \(i\)-я пара друзей имеет значение дружбы \(f_i\).
Учитель должен посетить \(k\) экскурсий, на каждой из которых она выбирает пару детей случайно, равновероятно и независимо. Если выбрана пара друзей, их значение дружбы увеличивается на \(1\) для всех последующих экскурсий (учитель может выбрать пару детей более одного раза). Значение дружбы пары детей, не являющихся друзьями, остается \(0\), и не изменяется для следующих экскурсий.
Найдите ожидаемое значение суммы значений дружбы по всем \(k\) парам, выбранным для экскурсий (в момент времени их выбора). Можно показать, что этот ответ всегда может быть выражен в виде дроби \(\dfrac{p}{q}\) где \(p\) и \(q\) взаимопростые целые числа. Посчитайте \(p\cdot q^{-1} \bmod (10^9+7)\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — ответ на задачу.
Примечание
В первом наборе входных данных, нет пар друзей, а значит значение дружбы всегда равно \(0\) и остается \(0\) после выбора экскурсий, следовательно, сумма значений по всем экскурсиям равна \(0\).
Во втором наборе входных данных, только одна возможная пара для выбора \((1, 2)\), и их значение дружбы изначально \(1\), значит их значение дружбы увеличивается каждую экскурсию на \(1\). Таким образом, сумма это \(1+2+3+\ldots+10 = 55\).
В третьем наборе входных данных ответ это \(\frac{7}{9} = 777\,777\,784\bmod (10^9+7)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
100 0 24
2 1 10
1 2 1
3 1 2
2 1 1
5 2 4
1 2 25
3 2 24
|
0
55
777777784
40000020
|