Carol 有一个由 $$$n$$$ 个非负整数组成的序列 $$$s$$$。她想和爱丽丝和鲍勃玩“猜猜游戏”。
为了玩游戏,Carol 将在 $$$[1, n]$$$ 范围内随机选择两个整数索引 $$$i_a$$$ 和 $$$i_b$$$,并设置 $$$a=s_{i_a}$$$、$$$b=s_{i_b}$$$。请注意,$$$i_a$$$ 和 $$$i_b$$$ 可能重合。
卡罗尔会告诉:
- $$$a$$$ 对 Alice 的价值;
- $$$b$$$ 对 Bob 的价值;
- Alice 和 Bob 的 $$$a \mid b$$$ 的值,其中 $$$|$$$ 表示按位 OR 运算。
请注意,Carol 不会向 Alice 或 Bob 透露有关 $$$s$$$ 的任何信息。
然后猜测开始。两名玩家轮流猜测,爱丽丝先开始。两名玩家的目标是确定以下哪一项为真:$$$a < b$$$、$$$a > b$$$ 或 $$$a = b$$$。
轮到玩家可以做以下两件事之一:
- 说“我不知道”,然后将回合交给其他玩家;
- 说“我知道”,然后回答“$$$a<b$$$”、“$$$a>b$$$”或“$$$a=b$$$”;然后游戏结束。
Alice 和 Bob 听到对方所说的话,并且可以使用此信息来推断答案。 Alice 和 Bob 都很聪明,只有在完全确定的情况下才会说“我知道”。
您需要计算玩家在游戏中进行的回合数的期望值。输出对 $$$998\,244\,353$$$ 取模的答案。
正式地,让 $$$M = 998\,244\,353$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$s_1,s_2,\ldots, s_n$$$ ($$$0 \le s_i < 2^{30}$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 问题的答案以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
4 2 2 3 3 0 0 0 3 9 9 6 8 34124838 0 113193378 8 321939321 113193378 9463828 99
输出 #1
499122179 1 332748120 77987843
注意
在第一个测试用例中,只有 $$$4$$$ 可能的情况:
1、$$$i_a=1$$$、$$$i_b=1$$$、$$$a=2$$$、$$$b=2$$$,圈数为$$$2$$$;
2、$$$i_a=1$$$、$$$i_b=2$$$、$$$a=2$$$、$$$b=3$$$,圈数为$$$3$$$;
3、$$$i_a=2$$$、$$$i_b=1$$$、$$$a=3$$$、$$$b=2$$$,圈数为$$$2$$$;
4. $$$i_a=2$$$、$$$i_b=2$$$、$$$a=3$$$、$$$b=3$$$,圈数为$$$3$$$。
预期圈数为 $$$\frac{2+3+2+3}{4}=\frac{5}{2}=499122179\pmod{998244353}$$$。
考虑第一种情况,当 $$$a=2$$$ 时,$$$b=2$$$。猜测过程如下。
在第一回合中,Alice 认为,“我知道 $$$a=2,a\mid b=2$$$。我可以推断 $$$b=0$$$ 或 $$$b=2$$$,但我不确定是哪一个”。因此,她说:“我不知道”。
在第二回合中,鲍勃认为,“我知道$$$b=2,a\mid b=2$$$。我可以推断$$$a=0$$$或$$$a=2$$$。但是如果$$$a=0$$$,那么爱丽丝在第一回合就已经说过$$$a<b$$$,但她没有。所以$$$a=2$$$”。因此,他说:“我知道,$$$a=b$$$”。游戏结束。
在第二个测试用例中,对于 $$$a=0$$$,$$$b=0$$$,Alice 立即知道 $$$a=b$$$。预期匝数等于 $$$1$$$。