Problem Description

A permutation of $(1, \ldots, 2^N)$, $(P_1, P_2, \ldots, P_{2^N})$ is given. Consider a tournament where $2^N$ players from player 1 to player $2^N$ compete in a knockout format. The tournament consists of $N$ rounds, conducted as follows:

• The first round consists of $2^{N-1}$ matches. In the $i$-th match $(1 \leq i \leq 2^{N-1})$, player $P_{2i-1}$ and player $P_{2i}$ compete.
• Subsequently, for $k = 2, \dots, N$, the $k$-th round is conducted as follows:
• The $k$-th round consists of $2^{N-k}$ matches. In the $i$-th match $(1 \leq i \leq 2^{N-k})$, the winner of the $(2i-1)$-th match in the $(k-1)$-th round and the winner of the $2i$-th match in the $(k-1)$-th round compete.

Each player is assigned a color, either red or blue, before the start of the tournament. All players may be assigned the same color.

Now, the following facts about the tournament results are known:

• In each match, if the opponents are assigned the same color, the player with the smaller player number wins.
• In each match, if the opponents are assigned different colors, the player with the larger player number wins.
• For $1 \leq i \leq M$, in some match, player $W_i$ and player $L_i$ compete, and player $W_i$ wins.

Output the number of ways to assign colors to the players that satisfy all the above conditions, modulo $998244353$. Note that it is possible that the information is incorrect, and there may be no way to assign colors that satisfies the conditions.

Input Format

The input is given from the standard input in the following format:

$N$ $M$ $P_1$ $\ldots$ $P_{2^N}$ $W_1$ $L_1$ $\vdots$ $W_M$ $L_M$

Output Format

Output the number of ways to assign colors that satisfy the conditions, modulo $998244353$.

Sample Input and Output

Sample Input #1

1 1
2 1
1 2

Sample Output #1

2

Sample Input #2

2 2
1 2 3 4
2 3
1 2

Sample Output #2

0

Notes/Hints

Constraints

• $1 \leq N \leq 17$
• $1 \leq M < 2^N$
• $1 \leq P_i \leq 2^N$
• All $P_i$ are distinct.
• $1 \leq W_i, L_i \leq 2^N$
• $W_i \neq L_i$
• All $(W_i, L_i)$ are distinct.
• All inputs are integers.

Sample Explanation 1

The tournament consists of only one match. Since player 1 and player 2 compete and player 1 wins, it is known that the two players were assigned the same color. Therefore, there are two possible color assignments for the two players: (red, red) and (blue, blue).

Sample Explanation 2

The only possible match where player 2 and player 3 can compete is the first match in the second round, so player 2 must have won in the first round. On the other hand, the only possible match where player 1 and player 2 can compete is the first match in the first round, but it is known that player 1 won there. Therefore, this situation is impossible, and there are zero ways to assign colors that satisfy the conditions.

见题面 Input 部分

见题面 Output 部分