CF2029H Message Spread

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

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} $ .

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 $ .