В школе Гомера есть \(n\) студентов, которые любят клубы.
Изначально есть \(m\) клубов, и каждый из \(n\) студентов находится ровно в одном клубе. Другими словами, в \(i\)-м клубе \(a_i\) студентов для \(1 \leq i \leq m\), причем \(a_1+a_2+\dots+a_m = n\).
\(n\) студентов настолько недружелюбны, что каждый день один (выбранный равновероятно среди всех \(n\) студентов) из них злится. Разозлившийся студент сделает одну из следующих вещей.
- С вероятностью \(\frac 1 2\) он покидает свой нынешний клуб, затем сам создает новый клуб и присоединяется к нему. В новом клубе, который он создает, есть только один ученик (он сам).
- С вероятностью \(\frac 1 2\) он не создает новый клуб. В этом случае он меняет свой клуб на некоторый (возможно, на тот же клуб, в котором он находится в настоящее время) с вероятностью, пропорциональной количеству студентов в нем. Формально, пусть есть \(k\) клубов, и в \(i\)-м клубе есть \(b_i\) студентов для \(1 \leq i \leq k\) (до того, как студент разозлится). Он покидает свой текущий клуб, а затем присоединяется к \(i\)-му клубу с вероятностью \(\frac {b_i} {n}\).
Отметим, что когда клуб становится пустым, студенты никогда не присоединятся к нему, потому что любой ученик, который разозлится, присоединится к пустому клубу с вероятностью \(0\) в соответствии с приведенным выше утверждением.
Гомер интересуется ожидаемым количеством дней до того момента, когда все студенты окажутся в одном и том же клубе впервые.
Мы можем доказать, что ответ может быть представлен в виде рационального числа \(\frac p q\) с \(\gcd(p, q) = 1\). Вы должны найти значение \(pq^{-1} \bmod 998\,244\,353\). Можно показать, что \(q \bmod 998\,244\,353 \neq 0\) при заданных ограничениях задачи.
Выходные данные
Выведите одно целое число — ожидаемое количество дней, пока все студенты не окажутся в одном клубе впервые, по модулю \(998\,244\,353\).
Примечание
В первом примере независимо от того, какой студент разозлится, два студента с вероятностью \(\frac 1 4\) попадут в один и тот же клуб. Таким образом, ожидаемое количество дней, пока каждый ученик не окажется в одном клубе, должно составлять \(4\).
Во втором примере мы отмечаем, что в первый день:
- Единственный студент в первом клубе разозлится с вероятностью \(\frac 1 3\). Если он разозлится, то создаст новый клуб и присоединится к нему с вероятностью \(\frac 1 2\) (в этом случае будет три клуба, в которых будут состоять \(0, 1, 2\) студента, соответственно); покинет свой текущий клуб и присоединится ко второму с вероятностью \(\frac 1 2 \cdot \frac 2 3 = \frac 1 3\), или останется с вероятностью \(\frac 1 2 \cdot \frac 1 3 = \frac 1 6\);
- Каждый из двух студентов во втором клубе разозлится с вероятностью \(\frac 1 3\). Если один из них разозлится, то создаст новый клуб и присоединится к нему с вероятностью \(\frac 1 2\), покинет свой текущий клуб и присоединится ко второму с вероятностью \(\frac 1 2 \cdot \frac 1 3 = \frac 1 6\), или останется с вероятностью \(\frac 1 2 \cdot \frac 2 3 = \frac 1 3\).
В четвертом примере изначально есть только один клуб. То есть каждый студент уже в одном клубе. Так что ответ — \(0\).