{"raw_statement":[{"iden":"background","content":"> 我们是未成熟的斗士 现在绝不认输\n>\n> 我们是未成熟的梦想家 现在绝不哭泣"},{"iden":"statement","content":"现给定一个无向完全图 $G(V,E)$ 和一个长度为 $|V|$ 的权值数组 $a$．$a_i$ 表示编号为 $i$ 的节点的权值．\n\n定义一条边 $e(u,v)$ 的边值为 $val(e)$，满足 $val(e)=a_u\\oplus a_v$，也就是边连接的两个节点的权值的异或和；定义 $G$ 的一个生成树 $T(V,E_t)$ 的权值为 $Val(T)$，满足 $Val(T)=\\sum_{e\\in E_t}val(e)$，也就是树上边的边权和．\n\n您需要求出 $\\sum_{T}Val(T)$．即 $G$ 中所有不同生成树的权值的和．\n\n我们认为两棵生成树是不同的，当且仅当两棵树的边集 $E_t$ 不完全相同，即至少存在一条边，满足其仅属于两棵生成树中的其中一棵．"},{"iden":"input","content":"包括两行．\n\n第一行是一个整数 $n$，表示 $|V|$，即节点个数．\n\n第二行是 $n$ 个整数，依次为 $a_1\\sim a_n$．"},{"iden":"output","content":"一行一个整数．表示你的答案对 $998244353$ 取模．"},{"iden":"note","content":"### 样例 #1 说明：\n考虑一共存在三个生成树 $\\{1-2-3\\},\\{1-3-2\\},\\{3-1-2\\}$．\n\n它们的权值分别为 $(1\\oplus 2)+(2\\oplus 3)=4,(1\\oplus 3)+(3\\oplus 2)=3,(3\\oplus 1)+(1\\oplus 2)=5$．\n\n有 $4+3+5=12$．\n\n### 数据点约束\n保证对于所有数据，$1\\le n\\le 10^6$，$0\\le a_i\\le 10^9$．\n|测试点编号|数据范围|特殊性质|\n|:-:|:-:|:-:|\n|$1$||所有 $a_i$ 相等|\n|$2\\sim 5$|$n\\le 4$||\n|$6\\sim 10$|$n\\le 300$||\n|$11\\sim 12$|$n\\le 5\\times 10^4$|$a_i=[i=1]$|\n|$11\\sim 15$|$n\\le 5\\times 10^4$||\n|$16\\sim 20$|||"}],"translated_statement":null,"sample_group":[["3\n1 2 3","12"],["6\n1 1 4 5 1 4","19008"],["10\n1 1 4 5 1 4 1 9 1 9","567022588"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}