E. 期望功率

时间限制：4 秒 内存限制：256 兆字节

给定一个包含 $n$ 个整数的数组 $a_1,a_2,\dots,a_n$。 同时给定一个数组 $p_1,p_2,\dots,p_n$。

设 $S$ 表示按照如下规则构造的随机多重集合（可以包含重复元素）：

• 初始时 $S$ 为空。
• 对于每个 $i$（从 $1$ 到 $n$），以概率 $\boldsymbol{\dfrac{p_i}{10^4}}$ 将 $a_i$ 插入 $S$ 中。每个元素的插入操作相互独立。

记 $f(S)$ 为集合 $S$ 中所有元素的按位异或和。 请计算 $\boldsymbol{(f(S))^2}$ 的期望值，答案对 $10^9+7$ 取模。

---

形式化输出要求

设模数 $M=10^9+7$。 可以证明答案能表示为既约分数 $\dfrac{p}{q}$。 你需要输出 $p\cdot q^{-1} \bmod M$，即满足以下条件的整数 $x$：

$$0\le x<M,\quad x\cdot q\equiv p \pmod M$$

---

输入格式

每个测试文件包含多组测试用例。 第一行输入测试用例数 $t$（$1\le t\le 10^4$）。

每组测试用例：

• 第一行：一个整数 $n$（$1\le n\le 2\cdot 10^5$）
• 第二行：$n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le 1023$）
• 第三行：$n$ 个整数 $p_1,p_2,\dots,p_n$（$1\le p_i\le 10^4$）

数据保证：所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。

---

输出格式

对于每组测试用例，输出 $(f(S))^2$ 的期望值，对 $10^9+7$ 取模。

---

样例输入

4
2
1 2
5000 5000
2
1 1
1000 2000
6
343 624 675 451 902 820
6536 5326 7648 2165 9430 5428
1
1
10000

样例输出

500000007
820000006
280120536
1

---

样例解释

第一个样例

$a=[1,2]$，每个元素被选中的概率为 $\dfrac{1}{2}$。 共有 $4$ 种等概率情况：

• $S=\emptyset$：$f(S)=0$，$(f(S))^2=0$
• $S=\{1\}$：$f(S)=1$，$(f(S))^2=1$
• $S=\{2\}$：$f(S)=2$，$(f(S))^2=4$
• $S=\{1,2\}$：$f(S)=1\oplus 2=3$，$(f(S))^2=9$

期望：

$$\dfrac{0+1+4+9}{4}=\dfrac{14}{4}=\dfrac{7}{2}\equiv 500000007 \pmod{10^9+7} $$

第二个样例

$a=[1,1]$，选中概率分别为 $0.1$ 和 $0.2$。 有效情况：

• 都不选：概率 $0.72$，贡献 $0$
• 恰好选一个：概率 $0.26$，贡献 $1$
• 都选：异或为 $0$，贡献 $0$

期望：$0.26=\dfrac{26}{100}\equiv 820000006 \pmod{10^9+7}$