За лінійністю математичного сподівання відповідь дорівнює сумі за всіма початковими піснями ймовірностей того, що пісню ще знають після вечорів. Усі пісні симетричні, тож відповідь дорівнює n \cdot s, де — ймовірність того, що одна фіксована пісня збережеться.
Стежитимемо за цією піснею, і нехай — кількість музикантів, які її знають; спочатку c = 1. Вечір змінює , лише якщо пісню знає рівно один із і . Якщо її знає , а не знає, то збільшується на одиницю; якщо її знає , а не знає, то зменшується на одиницю. Кожна з цих двох подій має ймовірність
а з імовірністю 1 - 2r_c нічого не змінюється. Наступне значення залежить лише від поточного, тож — ланцюг Маркова на станах 0, 1, \ldots, n, і пісня зникає назавжди саме тоді, коли досягає (тоді r_0 = 0).
Нехай — матриця переходів цього ланцюга розміру (n+1) \times (n+1): T_{c,c-1} = T_{c,c+1} = r_c і T_{c,c} = 1 - 2r_c. Розподіл після вечорів — це рядок матриці T^k, отже,
Усі обчислення можна виконувати одразу за модулем M = 998\,244\,353: імовірності r_c стають c(n-c) \cdot (n(n-1))^{-1} \bmod M, а піднесення матриці до степеня використовує лише додавання й множення, тож результат — саме потрібний лишок p \cdot q^{-1} \bmod M. Обчислимо T^k двійковим піднесенням до степеня: не більше ніж 2 \log_2 k \approx 120 множень матриць розміру не більше 101 \times 101. Зауважимо, що для потрібен 64-бітний тип. Зводити за модулем M - 1 не можна: матриця вироджена, тож мала теорема Ферма до неї не застосовна.
Складність — O(n^3 \log k).
Зауваження. Якщо дивитися назад у часі, родовідні лінії музикантів зливаються, як у коалесценті Кінгмена, і це дає замкнену формулу, яку можна обчислити за O(n \log k); тут вона не потрібна.