No submission language available for this problem.

Description

Input

The first line consists of an integer $N$ ($2 \le N \le 100\,000$).

The following line consists of $N$ integers $A_i$ ($1 \le A_i \le 100\,000$).

Output

Output an integer representing the number of ways to build two decks such that the game is balanced. Output the answer modulo $998\,244\,353$.

4
16 12 4 8

9

4
1 2 4 8

1

2
1 1

5

6
1 1 1 2 2 2

169

Note

Explanation for the sample input/output #1

Denote $S$ and $T$ as the set of cards in your deck and your friend's deck, respectively. There are $9$ ways to build the decks such that the game is balanced.

• $S = \{\}$ and $T = \{\}$. Both decks have the power of $0$.
• $S = \{2, 3, 4\}$ and $T = \{\}$. Both decks have the power of $0$.
• $S = \{\}$ and $T = \{2, 3, 4\}$. Both decks have the power of $0$.
• $S = \{2, 4\}$ and $T = \{3\}$. Both decks have the power of $4$.
• $S = \{3\}$ and $T = \{2, 4\}$. Both decks have the power of $4$.
• $S = \{2, 3\}$ and $T = \{4\}$. Both decks have the power of $8$.
• $S = \{4\}$ and $T = \{2, 3\}$. Both decks have the power of $8$.
• $S = \{3, 4\}$ and $T = \{2\}$. Both decks have the power of $12$.
• $S = \{2\}$ and $T = \{3, 4\}$. Both decks have the power of $12$.

Explanation for the sample input/output #2

The only way to make the game balanced is to have both decks empty.

Explanation for the sample input/output #3

There are $5$ ways to build the decks such that the game is balanced.

• $S = \{\}$ and $T = \{\}$. Both decks have the power of $0$.
• $S = \{1, 2\}$ and $T = \{\}$. Both decks have the power of $0$.
• $S = \{\}$ and $T = \{1, 2\}$. Both decks have the power of $0$.
• $S = \{1\}$ and $T = \{2\}$. Both decks have the power of $1$.
• $S = \{2\}$ and $T = \{1\}$. Both decks have the power of $1$.