{"problem":{"name":"[YsOI2023] Qingshan and Daniel 2","description":{"content":"今天 Ysuperman 发现了一款非对称博弈游戏，名字叫做 Bugaboo，具体规则如下： > 在游戏的一开始，Qingshan 手中有一个正整数集 $S$，Daniel 手中有一个正整数集 $T$。 > > Qingshan 和 Daniel 依次如下操作（Qingshan 先手）：选择在自己数集中的任意两个**不同的**数字 $x,y$，并且还需要满足 $|x-y|$ 不属于**对方的数集","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9537"},"statements":[{"statement_type":"Markdown","content":"今天 Ysuperman 发现了一款非对称博弈游戏，名字叫做 Bugaboo，具体规则如下：\n\n> 在游戏的一开始，Qingshan 手中有一个正整数集 $S$，Daniel 手中有一个正整数集 $T$。\n>\n> Qingshan 和 Daniel 依次如下操作（Qingshan 先手）：选择在自己数集中的任意两个**不同的**数字 $x,y$，并且还需要满足 $|x-y|$ 不属于**对方的数集**，然后将 $|x-y|$ 加入**对方的数集**。最终无法操作的人失败。\n>\n> 可以注意到在游戏的进行过程中一个人手中的数集是会不断变化的，他在选择数字 $x,y$ 时既可以选择初始自己拥有的数字，也可以选择后面新增的数字。\n\n现在 Ysuperman 给了你一个正整数集 $R$，Ysuperman 想要知道如果 Qingshan 一开始拥有的集合 $S$ 是 $R$ 的 $2^{|R|}$ 个子集中的任意一个，而 Daniel 一开始拥有的集合 $T$ 也是 $R$ 的 $2^{|R|}$ 个子集中的任意一个，那么在多少种情况下 Qingshan 会赢。\n\n由于答案可能很大， Ysuperman 不想为难你，于是只要你求出答案对 $998,244,353$ 取模后的结果。\n\n## Input\n\n第一行一个整数 $n$ 表示集合 $R$ 的大小。\n\n接下来一行 $n$ 个整数 $a_1,a_2,\\dots,a_n$ 表示集合 $R$ 中的所有数。\n\n## Output\n\n输出一行一个数表示答案对 $998,244,353$ 取模后的结果。\n\n[samples]\n\n## Background\n\nYsuperman 模板测试的博弈论题。\n\n都什么年代了，还在玩传统对称博弈，快来玩玩非传统非对称博弈。\n\n猜猜题目名称啥意思，没错就是要你快去做 CF1764B！！！另外这题融合了 CF1495、CF1707、CF1764 的梗（）\n\n## Note\n\n#### 样例 1 解释\n\n对于第一组样例，显然 Qingshan 要赢的一个必要条件是她一开始的集合有至少两个数：\n\n1. 当 $S=\\{1,2\\}$ 时，Qingshan 赢当 $T=\\{\\},\\{2\\},\\{3\\},\\{2,3\\}$。\n1. 当 $S=\\{1,3\\}$ 时，Qingshan 赢当 $T=\\{\\},\\{1\\},\\{3\\}$。\n1. 当 $S=\\{2,3\\}$ 时，Qingshan 赢当 $T=\\{\\},\\{3\\}$。\n1. 当 $S=\\{1,2,3\\}$ 时，Qingshan 赢当 $T=\\{\\},\\{1\\},\\{2\\},\\{3\\},\\{1,3\\},\\{2,3\\}$。\n\n所以答案为 $4+3+2+6=15$。\n\n#### 数据范围\n\n对于 $15\\%$ 的数据，有 $a_i\\le 10$。\n\n对于 $30\\%$ 的数据，有 $n\\le 10$。\n\n对于 $50\\%$ 的数据，有 $a_i\\le 1000$。\n\n对于 $70\\%$ 的数据，有 $n\\le 1000$。\n\n对于 $100\\%$ 的数据，有 $1\\le n\\le 20000$，$1\\le a_1