CF1925D Good Trip

There are $ n $ children in a class, $ m $ pairs among them are friends. The $ i $ -th pair who are friends have a friendship value of $ f_i $ . The teacher has to go for $ k $ excursions, and for each of the excursions she chooses a pair of children randomly, equiprobably and independently. If a pair of children who are friends is chosen, their friendship value increases by $ 1 $ for all subsequent excursions (the teacher can choose a pair of children more than once). The friendship value of a pair who are not friends is considered $ 0 $ , and it does not change for subsequent excursions. Find the expected value of the sum of friendship values of all $ k $ pairs chosen for the excursions (at the time of being chosen). It can be shown that this answer can always be expressed as a fraction $ \dfrac{p}{q} $ where $ p $ and $ q $ are coprime integers. Calculate $ p\cdot q^{-1} \bmod (10^9+7) $ .

N/A

N/A

For the first test case, there are no pairs of friends, so the friendship value of all pairs is $ 0 $ and stays $ 0 $ for subsequent rounds, hence the friendship value for all excursions is $ 0 $ . For the second test case, there is only one pair possible $ (1, 2) $ and its friendship value is initially $ 1 $ , so each turn they are picked and their friendship value increases by $ 1 $ . Therefore, the total sum is $ 1+2+3+\ldots+10 = 55 $ . For the third test case, the final answer is $ \frac{7}{9} = 777\,777\,784\bmod (10^9+7) $ .