题目描述
小Q学习位运算时发现了异或的秘密。
小Q是一个热爱学习的人,他经常去维基百科学习计算机科学。
就在刚才,小Q认真地学习了一系列位运算符,其中按位异或的
运算符 ⊕ 对他影响很大。按位异或的运算符是双目运算符。按位异或具有交换律,即 i⊕j=j⊕i。
他发现,按位异或可以理解成被运算的数字的二进制位对应位如果相同,则结果的该位置为 0,否则为 1,例如 1(01)⊕2(10)=3(11)。
他还发现,按位异或可以理解成数字的每个二进制位进行了不进位的加法,例如 3(11)⊕3(11)=0(00)。
于是他想到了两个关于异或的问题,这两个问题基于一个给定的非负整数序列A1,A2,…,An,其中 n 是该序列的长度。
第一个问题是,如果用 fi,j 表示 Ai⊕Ai+1⊕⋯⊕Aj,则任意的 1≤i≤j≤n 的 fi,j 相加是多少。
第二个问题是,如果用 gi,j 表示 Ai+Ai+1+⋯+Aj,则任意的 1≤i≤j≤n 的 gi,j 异或在一起是多少。
比如说,对于序列 1,2,所有的 f 是 {1,2,1⊕2},加起来是 6;所有的 g 是 {1,2,1+2},异或起来是 0。
他觉得这两个问题都非常的有趣,所以他找到了你,希望你能快速解决这两个问题,其中第一个问题的答案可能很大,你只需要输出它对 998244353(一个质数)取模的值即可。
输入格式
第一行一个正整数 n,表示序列的长度。
第二行 n 个非负整数 A1,A2,…,An,表示这个序列。
输出格式
两个整数,表示两个问题的答案,空格隔开,其中第一个问题的答案要对 998244353(一个质数)取模。
2
1 2
6 0
数据范围
对于 100% 的数据满足 n≤105,Ai≤106。