题目描述

小奶龙和天才少年小七正在玩一个游戏。

游戏开始时，小七拥有一个正整数集合 $S$，奶龙拥有一个正整数集合 $T$。

小七和奶龙轮流进行操作，小七先手。轮到一名玩家时，他需要：

1. 从自己的集合中选择两个不同的数 $x,y$；
2. 要求 $|x-y|$ 不属于对方的集合；
3. 将 $|x-y|$ 加入对方的集合。

无法进行操作的玩家失败。

注意，在游戏过程中，双方的集合会不断变化。选择 $x,y$ 时，既可以选择初始拥有的数，也可以选择后续加入集合的数。

现在给定一个正整数集合 $R$。

小七的初始集合 $S$ 可以是 $R$ 的任意一个子集，奶龙的初始集合 $T$ 也可以是 $R$ 的任意一个子集。也就是说，$(S,T)$ 一共有

种可能。

求其中有多少种初始情况会使小七获胜。

答案对

取模。

输入格式

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

第二行包含 $n$ 个整数

表示集合 $R$ 中的所有元素。

输出格式

输出一行一个整数，表示小七获胜的初始情况数量，对 $998244353$ 取模后的结果。

样例 1

输入

3
1 2 3

输出

15

样例 2

输入

5
6 8 10 17 19

输出

378

样例 3

输入

9
2 3 4 6 7 8 12 16 18

输出

106533

样例解释

对于样例 1，小七获胜的一个必要条件是初始集合 $S$ 中至少有两个数。

1. 当 $S=\{1,2\}$ 时，若

   $$T\in\{\varnothing,\{2\},\{3\},\{2,3\}\},$$

   小七获胜，共 $4$ 种情况；

2. 当 $S=\{1,3\}$ 时，若

   $$T\in\{\varnothing,\{1\},\{3\}\},$$

   小七获胜，共 $3$ 种情况；

3. 当 $S=\{2,3\}$ 时，若

   $$T\in\{\varnothing,\{3\}\},$$

   小七获胜，共 $2$ 种情况；

4. 当 $S=\{1,2,3\}$ 时，若

   $$T\in\{\varnothing,\{1\},\{2\},\{3\},\{1,3\},\{2,3\}\},$$

   小七获胜，共 $6$ 种情况。

因此共有

种初始情况使小七获胜。

数据范围

• 对于 $15\%$ 的数据，$a_i\le 10$；

• 对于 $30\%$ 的数据，$n\le 10$；

• 对于 $50\%$ 的数据，$a_i\le 1000$；

• 对于 $70\%$ 的数据，$n\le 1000$；

• 对于全部测试数据：

  $$1\le n\le 20000,$$ $$1\le a_1<a_2<\cdots<a_n\le 20000.$$