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.

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