Given is an undirected graph with $$$n$$$ vertices and $$$m$$$ edges. Each edge connects two vertices $$$(u, v)$$$ and has a probability of $$$\frac{p}{q}$$$ of appearing each day.
Initially, vertex $$$1$$$ has a message. At the end of the day, a vertex has a message if and only if itself or at least one of the vertices adjacent to it had the message the day before. Note that each day, each edge chooses its appearance independently.
Calculate the expected number of days before all the vertices have the message, modulo $$$998\,244\,353$$$.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\leq n\leq 21$$$, $$$n-1\leq m\leq\frac{n(n-1)}{2}$$$).
Then $$$m$$$ lines follow, each containing four integers $$$u$$$, $$$v$$$, $$$p$$$, and $$$q$$$ ($$$1\leq u\neq v\leq n$$$, $$$1\leq p<q<998\,244\,353$$$, $$$\gcd(p,q)=1$$$) — there is an undirected edge between $$$u$$$ and $$$v$$$, and it has a probability of appearance of $$$\frac{p}{q}$$$ each day.
It is guaranteed that there are no self-loops or multiple-edges in the graph and that the graph is connected if all of the edges appear.
Additional constraint in the input: Let $$$g_{i,j}$$$ be the probability of appearance of the edge between $$$i$$$ and $$$j$$$ ($$$g_{i,j}=0$$$ if there is no edge between $$$i$$$ and $$$j$$$). It is guaranteed that for any $$$S\subseteq\{1,2,\ldots,n\}$$$ ($$$|S|\ge 1$$$), $$$$$$ \prod_{i\in S}\left(\prod_{j\in\{1,2,\ldots,n\}\setminus S}(1-g_{i,j})\right)\not\equiv1\pmod{998\,244\,353}. $$$$$$
Print a single integer in the only line of the output — the expected number of days, modulo $$$998\,244\,353$$$.
Formally, let $$$M = 998\,244\,353$$$. It can be shown that the exact answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.
2 11 2 1 10
10
3 31 2 1 21 3 1 22 3 1 2
887328316
1 0
0
5 81 2 1 111 3 2 111 4 3 111 5 4 112 4 5 112 5 6 113 4 7 114 5 8 11
469993557
21 221 2 3 42 3 4 53 4 5 65 6 7 86 7 8 97 8 9 108 9 2 39 10 3 410 11 4 511 12 5 612 13 6 713 14 7 814 15 8 915 16 9 1016 17 2 317 18 3 418 19 4 519 20 5 620 21 6 71 10 100 100115 4 147 2204 11 1 998244352
299529765
In the first test, the answer is equal to the expected number of days before the only edge in the graph first appears, and that is $$$\frac{1}{0.1}=10$$$.
In the second test, the answer is equal to $$$\frac{20}{9}$$$ before it is taken modulo $$$998\,244\,353$$$.
In the third test, the only vertex already has the message, so the answer is $$$0$$$.
Name |
---|