I. Cyclic Melody
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice, a talented pianist, just composed a perfect melody! A melody is a sequence of $$$n$$$ notes $$$a_1, a_2, ..., a_n$$$, represented as integers. This melody is cyclic, meaning that the $$$n$$$th note is adjacent to the first note. Further, a perfect melody is one such that each pair of adjacent notes different in value by exactly $$$1$$$. (Formally, $$$|a_i - a_{(i \bmod n) + 1}| = 1$$$ for all $$$i \in \{1, 2, ..., n\}$$$)

Alice was just about to play the melody when Bob showed up and scrambled all the notes! Given an arbitrary ordering of the notes, help Alice determine the number of perfect melodies she can form by rearranging the notes. Two rearrangements are considered unique if for some $$$i$$$, the $$$i$$$-th element in the original ordering ends up in different positions between the two rearrangements.

Input

The first line of input will contain $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of notes in the melody.

The next line of input will contain $$$n$$$ space-separated integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \leq a_i \leq 10^6$$$) — the (unordered) sequence of notes in the melody.

Output

Output a single integer, representing the number of ways that the notes can be arranged into a perfect melody. Since this number may be very large, output it modulo $$$998244353$$$.

Examples
Input
4
2 2 1 3
Output
8
Input
3
1 2 3
Output
0
Input
8
1 2 3 2 3 4 3 2
Output
576