题目背景

Ysuperman 模板测试的博弈论题。

都什么年代了，还在玩传统对称博弈，快来玩玩非传统非对称博弈。

猜猜题目名称啥意思，没错就是要你快去做 CF1764B！！！另外这题融合了 CF1495、CF1707、CF1764 的梗（）

题目描述

今天 Ysuperman 发现了一款非对称博弈游戏，名字叫做 Bugaboo，具体规则如下：

在游戏的一开始，Qingshan 手中有一个正整数集 $S$，Daniel 手中有一个正整数集 $T$。

Qingshan 和 Daniel 依次如下操作（Qingshan 先手）：选择在自己数集中的任意两个不同的数字 $x,y$，并且还需要满足 $|x-y|$ 不属于对方的数集，然后将 $|x-y|$ 加入对方的数集。最终无法操作的人失败。

可以注意到在游戏的进行过程中一个人手中的数集是会不断变化的，他在选择数字 $x,y$ 时既可以选择初始自己拥有的数字，也可以选择后面新增的数字。

现在 Ysuperman 给了你一个正整数集 $R$，Ysuperman 想要知道如果 Qingshan 一开始拥有的集合 $S$ 是 $R$ 的 $2^{|R|}$ 个子集中的任意一个，而 Daniel 一开始拥有的集合 $T$ 也是 $R$ 的 $2^{|R|}$ 个子集中的任意一个，那么在多少种情况下 Qingshan 会赢。

由于答案可能很大， Ysuperman 不想为难你，于是只要你求出答案对 $998,244,353$ 取模后的结果。

输入格式

第一行一个整数 $n$ 表示集合 $R$ 的大小。

接下来一行 $n$ 个整数 $a_1,a_2,\dots,a_n$ 表示集合 $R$ 中的所有数。

输出格式

输出一行一个数表示答案对 $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

提示

样例 1 解释

对于第一组样例，显然 Qingshan 要赢的一个必要条件是她一开始的集合有至少两个数：

1. 当 $S=\{1,2\}$ 时，Qingshan 赢当 $T=\{\},\{2\},\{3\},\{2,3\}$。
2. 当 $S=\{1,3\}$ 时，Qingshan 赢当 $T=\{\},\{1\},\{3\}$。
3. 当 $S=\{2,3\}$ 时，Qingshan 赢当 $T=\{\},\{3\}$。
4. 当 $S=\{1,2,3\}$ 时，Qingshan 赢当 $T=\{\},\{1\},\{2\},\{3\},\{1,3\},\{2,3\}$。

所以答案为 $4+3+2+6=15$。

数据范围

对于 $15\%$ 的数据，有 $a_i\le 10$。

对于 $30\%$ 的数据，有 $n\le 10$。

对于 $50\%$ 的数据，有 $a_i\le 1000$。

对于 $70\%$ 的数据，有 $n\le 1000$。

对于 $100\%$ 的数据，有 $1\le n\le 20000$，$1\le a_1<a_2<\cdots<a_n\le 20000$。