Problem Statement

There are $2N$ people numbered $1$ through $2N$. The height of Person $i$ is $h_i$.

How many ways are there to make $N$ pairs of people such that the following conditions are satisfied? Compute the answer modulo $998,244,353$.

• Each person is contained in exactly one pair.
• For each pair, the heights of the two people in the pair are different.

Two ways are considered different if for some $p$ and $q$, Person $p$ and Person $q$ are paired in one way and not in the other.

Constraints

• $1 \\leq N \\leq 50,000$
• $1 \\leq h_i \\leq 100,000$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $h_1$ $:$ $h_{2N}$

Output

Print the answer.

Sample Input 1

2
1
1
2
3

Sample Output 1

2

There are two ways:

• Form the pair (Person $1$, Person $3$) and the pair (Person $2$, Person $4$).
• Form the pair (Person $1$, Person $4$) and the pair (Person $2$, Person $3$).

Sample Input 2

5
30
10
20
40
20
10
10
30
50
60

Sample Output 2

516