Initially, we had one array, which was a permutation of size $n$ (an array of size $n$ where each integer from $1$ to $n$ appears exactly once).

We performed $q$ operations. During the $i$-th operation, we did the following:

• choose any array we have with at least $2$ elements;
• split it into two non-empty arrays (prefix and suffix);
• write two integers $l_i$ and $r_i$, where $l_i$ is the maximum element in the left part which we get after the split, and $r_i$ is the maximum element in the right part;
• remove the array we've chosen from the pool of arrays we can use, and add the two resulting parts into the pool.

For example, suppose the initial array was $[6, 3, 4, 1, 2, 5]$, and we performed the following operations:

1. choose the array $[6, 3, 4, 1, 2, 5]$ and split it into $[6, 3]$ and $[4, 1, 2, 5]$. Then we write $l_1 = 6$ and $r_1 = 5$, and the arrays we have are $[6, 3]$ and $[4, 1, 2, 5]$;
2. choose the array $[4, 1, 2, 5]$ and split it into $[4, 1, 2]$ and $[5]$. Then we write $l_2 = 4$ and $r_2 = 5$, and the arrays we have are $[6, 3]$, $[4, 1, 2]$ and $[5]$;
3. choose the array $[4, 1, 2]$ and split it into $[4]$ and $[1, 2]$. Then we write $l_3 = 4$ and $r_3 = 2$, and the arrays we have are $[6, 3]$, $[4]$, $[1, 2]$ and $[5]$.

You are given two integers $n$ and $q$, and two sequences $[l_1, l_2, \dots, l_q]$ and $[r_1, r_2, \dots, r_q]$. A permutation of size $n$ is called valid if we can perform $q$ operations and produce the given sequences $[l_1, l_2, \dots, l_q]$ and $[r_1, r_2, \dots, r_q]$.

Calculate the number of valid permutations.

The first line contains two integers $n$ and $q$ ($1 \le q < n \le 3 \cdot 10^5$).

The second line contains $q$ integers $l_1, l_2, \dots, l_q$ ($1 \le l_i \le n$).

The third line contains $q$ integers $r_1, r_2, \dots, r_q$ ($1 \le r_i \le n$).

Additional constraint on the input: there exists at least one permutation which can produce the given sequences $[l_1, l_2, \dots, l_q]$ and $[r_1, r_2, \dots, r_q]$.

Print one integer — the number of valid permutations, taken modulo $998244353$.