Problem Statement

A sequence X is called good when the following holds.

• X can be emptied by repeating the following operation zero or more times.
• Delete two adjacent elements x_i and x_{i+1} of X such that $x_i \neq x_{i+1}$.

You are given a sequence with 2N elements: $A=(a_1,\ldots,a_{2N})$.
Among the 2^{2N-1} ways to divide A into one or more contiguous subsequences, how many are such that all those contiguous subsequences are good? Find the count modulo 998244353.

Input

The input is given from Standard Input in the following format:
N
$a_1 \ldots a_{2N}$

Output

Print the answer.

Constraints

• $1 \leq N \leq 5 \times 10^5$
• $1 \leq a_i \leq 2N$
• All values in the input are integers.

Sample Input 1

3
1 1 2 3 4 5

Sample Output 1

2

The following two divisions satisfy the condition.

• (1,1,2,3,4,5)
• (1,1,2,3),(4,5)

Sample Input 2

1
1 2

Sample Output 2

1

Sample Input 3

1
1 1

Sample Output 3

0

Sample Input 4

12
4 2 17 12 18 15 17 4 22 6 9 20 21 16 23 16 13 2 20 15 16 3 7 15

Sample Output 4

2048

见题面 Input 部分

见题面 Output 部分