26219번 - 별꽃의 세레나데 (Hard)

겨울 나라의 왕은 꽃을 좋아하는 왕비를 위해 가장 아름다운 꽃들을 모아 화관을 만들기로 했다. 왕비가 좋아하는 꽃들은 특별해서 마법의 씨앗을 심은 뒤 별빛을 받아야 피어난다. 마법의 씨앗에서 피어날 수 있는 꽃들의 종류는 $N$가지이며, $i$번째 종류의 꽃이 피어날 확률은 $p_{i}$이다. 씨앗에서 꽃이 피어날 확률은 다른 씨앗에 영향을 받지 않는다. 화관을 만들기 위해서는 $i$번째 종류의 꽃이 각각 최소 $M_{i}$ 송이씩 필요하다. 화관이 만들어질 때까지 씨앗에서 꽃을 한 송이씩 피운다면, 필요한 씨앗 개수의 기댓값은 얼마일까?

첫 줄에 꽃들의 종류의 수를 의미하는 정수 $N$ ($1 \leq N \leq 6$) 이 주어진다.

다음 $N$개의 줄에 $i$번째 종류의 꽃이 필요한 개수인 정수 $M_{i}$ ($1 \leq M_{i} \leq 10$)과, 그 꽃이 피어날 확률의 비중을 의미하는 정수 $a_{i}$가 주어진다. $0 < a_{i} \leq 100,000$이며, 이것은 꽃이 피어날 확률 $p_{i}$가 $a_{i} / (\sum_{i=1}^{N} a_{i})$임을 나타낸다.

화관을 만들기 위해서 필요한 씨앗 개수의 기댓값을 출력한다. 구체적으로, 문제의 조건 하에 해당 값은 항상 $0$보다 큰 유리수임을 증명할 수 있다. 이 값을 서로소인 두 양의 정수 $P$, $Q$에 대해 $P/Q$로 나타내면, $R \times Q \equiv P \mod 998244353$이면서 $0 \leq R < 998244353$인 정수 $R$이 유일하게 존재한다. 이 $R$을 출력한다.