Problem I
Infinitely Long Game

Alice and Bob will play in a directed graph $H$. The $i$-th vertex in $H$ initially has a value $Y_ i$. The game will proceed as follows.

If $H$ contains a cycle, then the game is a tie.

Otherwise, Alice and Bob will take turns to choose a vertex in $H$ to start a chain. Alice starts first. Each player will do all of the following in their turn:

• Choose a vertex $v$ in $H$ that has a value $x$ strictly greater than $0$.

• Choose any directed path $P$ starting from $v$ in $H$. Note that since the graph is acyclic, all such paths $P$ is simple. A path is a sequence of vertices $v = v_1, v_2, \ldots , v_ k$ such that $(v_ i, v_{i+1})$ is an edge in $H$ for all $1 \leq i \leq k-1$.

• For every vertex $u \in P$, do the following:

  • If $u = v$, the player can change the value of vertex $v$ to any non-negative value strictly less than $x$. In other words, the player chooses a value $y$ such that $0 \leq y < x$, and sets the value of vertex $v$ to $y$.

  • Otherwise, the player can change the value of vertex $u$ to any non-negative value.

The player who cannot make a move loses the game.

Note that, because a player can change the value of a vertex to an arbitrarily large value, the number of moves in a game might be unbounded; i.e., “infinite”. However, it turns out that the game will eventually always end; i.e., “finite”. We shall leave this philosophical question of the “finite” and “infinite” nature of the game to the reader.

We want to find out if Bob can win the game, assuming both players play optimally.

There’s a twist: the author of this problem is too lazy to generate strong test cases, so the graph $H$ and initial values $Y_ i$ are generated randomly, according to the following rules.

You are given a simple undirected graph $G = (V, E)$ (with no self-loops, and the graph is not necessarily connected) with $N$ vertices and $M$ edges. The vertices are numbered from $1$ to $N$, where vertex $i$ has a value $X_ i$. Each edge $j$ also has a value $A_ j$, $B_ j$, and $C_ j$.

Create the directed graph $H$ and values $Y_ i$ as follows:

• The vertices of $H$ are the same as the vertices of $G$.

• For each vertex $v \in H$, the value of vertex $v$ is a independent random integer uniformly chosen between $0$ and $X_ v$, inclusive.

• For each edge $(u, v) \in E$, exactly one of the following will happen:

  • with probability $\frac{A_ i}{A_ i + B_ i + C_ i}$, add a directed edge from $u$ to $v$ in $H$;

  • with probability $\frac{B_ i}{A_ i + B_ i + C_ i}$, add a directed edge from $v$ to $u$ in $H$;

  • with probability $\frac{C_ i}{A_ i + B_ i + C_ i}$, do nothing.

Now, the problem becomes: given the graph $G$ and the values $X_ i$, $A_ i$, $B_ i$, and $C_ i$, find the probability that Bob wins the game, modulo $998\, 244\, 353$. It can be proven that the probability that Bob wins the game can be represented as an irreducible fraction $\frac{P}{Q}$, where $P$ and $Q$ are integers, and $Q$ is coprime to $998\, 244\, 353$. You need to output the value of $P \cdot Q^{-1} \bmod 998\, 244\, 353$.

Input

The first line of input contains two integers $N$ $(1 \leq N \leq 12)$ and $M$ $(0 \leq M \leq \frac{N(N-1)}{2})$, the number of vertices and edges in the graph $G$.

The next line contains $N$ integers $X_1, X_2, \ldots , X_ N$ $(0 \leq X_ i < 998\, 244\, 353 - 1)$, the values of the vertices in $G$.

The next $M$ lines each contain five integers $u_ i$, $v_ i$, $A_ i$, $B_ i$, and $C_ i$ $(1 \leq u_ i, v_ i \leq N$, $0 \leq A_ i, B_ i, C_ i < 998\, 244\, 353$, $1 \leq A_ i + B_ i + C_ i < 998\, 244\, 353)$, representing an edge $(u_ i,v_ i)$ in $G$.

Output

Output a single integer, the probability that Bob wins the game, modulo $998\, 244\, 353$.

Explanation

In the first sample, there are $24$ possible games $(H, Y)$ generated. The probability that Bob wins the game is $\frac{1}{4} \equiv 748\, 683\, 265 \pmod{998\, 244\, 353}$.

3 0
1 2 3

748683265

4 6
1 2 3 4
1 3 42 42 42
1 4 3 3 3
1 2 2 2 2
3 4 3 3 3
2 4 3 3 3
2 3 42 42 42

597577278