问题描述

在奥特曼的世界中，集合论是一种用来理解和描述各种事物和现象的理论工具。盖亚奥特曼发现，集合论可以帮助他更好地理解自己和宇宙，因此他对这个领域产生了浓厚的兴趣。

盖亚奥特曼对集合论的热爱始于他对各种不同类型事物的思考。他发现，无论是生物、非生物、星球、星系，甚至是各种概念和思想，都可以被视为集合的一种形式。他开始探索这些集合的特性、关系和规律，并尝试用集合论来描述和理解他所遇到的各种现象。

现在，盖亚奥特曼希望你能帮助他解决以下集合论问题。

给定长度为 $n$ 的非负整数序列 $\{a\}$，要求将序列 $\{a\}$ 分成 $2$ 个可重集合 $A,B$，满足每个元素在 $A$ 集合或 $B$ 集合，恰有 $2^n$ 种划分方式，现在额外要求集合 $A$ 中所有元素或运算的权值与集合 $B$ 中所有元素或运算的权值相同，特别地，当集合为空时，定义其所有元素的或运算权值为 $0$，请求满足条件的方案数，答案对 $998244353$ 取模。

输入格式

第一行包含 $1$ 个正整数 $n$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示序列 $a$。

输出格式

输出共 $1$ 行，输出 $1$ 个整数，表示最终答案，答案对 $998244353$ 取模。

样例输入输出

4
4 5 6 7

4

评测用例规模与规定

对于$20\%$的数据，$1\leq n \leq 10$。

对于$100\%$的数据，$1\leq n \leq 200$,$0 \leq a_i < 2^{15}$。

运行限制

• 最大运行时间：$2s$
• 最大运行内存：$256M$