P9537 [YsOI2023] Qingshan and Daniel 2

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.

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$.

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 one line with one number, representing the answer modulo $998,244,353$.

#### 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\}$. 1. When $S=\{1,3\}$, Qingshan wins when $T=\{\},\{1\},\{3\}$. 1. When $S=\{2,3\}$, Qingshan wins when $T=\{\},\{3\}$. 1. 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