Problem Background

Ysuperman's template test for game theory problems.

In this era, traditional symmetric games are outdated. It's time to try unconventional asymmetric games.

Guess what the problem title means. Yes, it's urging you to solve CF1764B! Additionally, this problem incorporates references from CF1495, CF1707, and CF1764.

Problem Description

Today, Ysuperman discovered an asymmetric game called Bugaboo with the following rules:

At the beginning of the game, Qingshan has a set of positive integers \( S \), and Daniel has a set of positive integers \( T \).

Qingshan and Daniel take turns performing the following operation (Qingshan goes first): Select any two different numbers \( x, y \) from their own set, and ensure that \( |x - y| \) is not in the opponent's set. Then, add \( |x - y| \) to the opponent's set. The person who cannot make a move loses.

Note that the set of numbers in one's hand changes during the game. When choosing numbers \( x, y \), one can select from the initial numbers or the newly added numbers.

Now, Ysuperman gives you a set of positive integers \( R \). Ysuperman wants to know how many scenarios result in Qingshan winning, where \( S \) and \( T \) are any of the \( 2^{|R|} \) subsets of \( R \).

Since the answer may be very large, Ysuperman does not want to make it difficult for you. Therefore, you only need to output the result modulo \( 998,244,353 \).

Input Format

The first line contains an integer \( n \), representing the size of the set \( R \).

The next line contains \( n \) integers \( a_1, a_2, \dots, a_n \), representing the elements of the set \( R \).

Output Format

Output a single integer, which is the result modulo \( 998,244,353 \).

Sample Input and Output

Sample Input #1

3
1 2 3

Sample Output #1

15

Sample Input #2

5
6 8 10 17 19

Sample Output #2

378

Sample Input #3

9
2 3 4 6 7 8 12 16 18

Sample Output #3

106533

Notes

Sample 1 Explanation

For the first sample, it is clear that a necessary condition for Qingshan to win is that her initial set has at least two numbers:

1. When \( S = \{1, 2\} \), Qingshan wins when \( T = \{\}, \{2\}, \{3\}, \{2, 3\} \).
2. When \( S = \{1, 3\} \), Qingshan wins when \( T = \{\}, \{1\}, \{3\} \).
3. When \( S = \{2, 3\} \), Qingshan wins when \( T = \{\}, \{3\} \).
4. When \( S = \{1, 2, 3\} \), Qingshan wins when \( T = \{\}, \{1\}, \{2\}, \{3\}, \{1, 3\}, \{2, 3\} \).

Thus, the answer is \( 4 + 3 + 2 + 6 = 15 \).

Data Range

For 15% of the data, \( a_i \leq 10 \).

For 30% of the data, \( n \leq 10 \).

For 50% of the data, \( a_i \leq 1000 \).

For 70% of the data, \( n \leq 1000 \).

For 100% of the data, \( 1 \leq n \leq 20000 \), \( 1 \leq a_1 < a_2 < \cdots < a_n \leq 20000 \).

见题面 Input 部分

见题面 Output 部分