Pokemons are planning their travel to the new region Galar. However, it is difficult to allow all of them to go there due to limited funds. There are n pokemons all over the world, numbered from 1 to n. We decide who can go to Galar according to the following rules. We start with a cactus having n vertices and m bidirectional edges, where the i-th vertex represents the pokemon i and each edge has a probability to go through. Pokemons go to Galar in rounds. In the first round, only the pokemon 1 is allowed to go to Galar. In the i-th round (i=2,3,…
Pokemons are planning their travel to the new region Galar. However, it is difficult to allow all of them to go there due to limited funds. There are n pokemons all over the world, numbered from 1 to n. We decide who can go to Galar according to the following rules. We start with a cactus (i.e. a connected graph in which every edge belongs to at most one simple cycle) having n vertices and m bidirectional edges, where the i-th vertex represents the pokemon i and each edge has a probability to go through. Pokemons go to Galar in rounds. In the first round, only the pokemon 1 is allowed to go to Galar. In the i-th round (i=2,3,…i = 2, 3, ldotsi=2,3,…), if pokemon u has got the permission to Galar in the (i - 1)-th round, pokemon v hasn't got the permission yet, and there is an edge between pokemon u and pokemon v with probability w to go through, then pokemon v will have a probability w to go to Galar in this round. If there is no pokemon that can get permission, the further rounds will be skipped. You can see the note after the sample for better understanding of this procedure. Please calculate the expected population of pokemons that can travel to Galar. In order to avoid precision issues, output the expected value modulo 998244353. Formally, let the answer be pqfrac{p}{q}qp, you need to output the minimum non-negative integer r satisfying that p≡qr(mod998244353)p equiv q r pmod{998244353}p≡qr(mod998244353). For example, 9≡4×748683267(mod998244353)9 equiv 4 times 748683267 pmod{998244353}9≡4×748683267(mod998244353).
