Problem Statement

You are creating an electrical circuit using $N$ parts numbered $1$ to $N$ and $M$ cables. These parts have a total of $M$ red terminals and $M$ blue terminals, with the $i$-th red terminal attached to part $R_i$ and the $i$-th blue terminal attached to part $B_i$. Each cable connects one red terminal and one blue terminal. In particular, it is allowed to connect two terminals attached to the same part. You cannot connect two or more cables to a terminal. Therefore, there are $M!$ ways in total to connect the $M$ cables (the cables are not distinguished from each other).

Let $s$ be the number of connected components when seeing this circuit as a graph with parts as vertices and cables as edges. Find the expected value, modulo $998244353$, of $s$ when randomly choosing the way to connect the $M$ cables out of the $M!$ ways.

What does it mean to find an expected value modulo $998244353$? It can be proved that the sought expected value is always a rational number. Also, under the constraints of this problem, it can be proved that when this value is expressed as $\frac{P}{Q}$ using two coprime integers $P$ and $Q$, there is exactly one integer $R$ that satisfies $R \times Q \equiv P\pmod{998244353}$ and $0 \leq R \lt 998244353$. Find this $R$.

Constraints

• $1\leq N \leq 17$
• $1 \leq M \leq 10^5$
• $1 \leq R_i, B_i \leq N$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
R_1 R_2 \dots R_M
B_1 B_2 \dots B_M

Output

Print the expected value of $s$, modulo $998244353$.