Background

A game theory problem for Ysuperman’s template test.

What era is it now? People are still playing traditional symmetric games. Come and try a non-traditional asymmetric game.

Guess what the title means. That’s right: it is telling you to go do CF1764B!!! Also, this problem mixes memes from CF1495, CF1707, and CF1764.

Problem Description

Today, Ysuperman discovered an asymmetric game called Bugaboo. The rules are as follows:

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

Qingshan and Daniel take turns performing the following operation (Qingshan moves first): choose any two different numbers $x,y$ from your own set, and it must also satisfy that $|x-y|$ does not belong to the other player’s set. Then add $|x-y|$ into the other player’s set. The player who cannot make a move loses.

Note that during the game, a player’s set will keep changing. When choosing $x,y$, the player may choose numbers originally in their set, or numbers added later.

Now Ysuperman gives you a set $R$ of positive integers. Ysuperman wants to know: if Qingshan’s initial set $S$ can be any of the $2^{|R|}$ subsets of $R$, and Daniel’s initial set $T$ can also be any of the $2^{|R|}$ subsets of $R$, then in how many cases will Qingshan win.

Since the answer may be very large, you only need to output the result modulo $998,244,353$.

Input Format

The first line contains an integer $n$, which is the size of set $R$.

The next line contains $n$ integers $a_1,a_2,\dots,a_n$, representing all numbers in set $R$.

Output Format

Output one line with one number, representing the answer modulo $998,244,353$.

3
1 2 3

15

5
6 8 10 17 19

378

9
2 3 4 6 7 8 12 16 18

106533

Hint

Explanation for Sample 1

For the first sample, it is clear that a necessary condition for Qingshan to win is that her initial set contains 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\}$.

So the answer is $4+3+2+6=15$.

Constraints

For $15\%$ of the testdata, $a_i\le 10$.

For $30\%$ of the testdata, $n\le 10$.

For $50\%$ of the testdata, $a_i\le 1000$.

For $70\%$ of the testdata, $n\le 1000$.

For $100\%$ of the testdata, $1\le n\le 20000$, $1\le a_1<a_2<\cdots<a_n\le 20000$.

Translated by ChatGPT 5