E. Матожидание квадрата
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив, состоящий из $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$. Также дан массив $$$p_1, p_2, \ldots, p_n$$$.

Через $$$S$$$ обозначим случайное мультимножество (т. е. оно может содержать равные элементы), которое строится следующим образом:

  • Изначально $$$S$$$ пусто.
  • Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ добавить $$$a_i$$$ в $$$S$$$ с вероятностью $$$\frac{p_i}{10^4}$$$. Обратите внимание, что каждый элемент добавляется независимо.

Пусть $$$f(S)$$$ равно результату применения побитового исключающего ИЛИ ко всем элементам $$$S$$$. Найдите математическое ожидание величины $$$(f(S))^2$$$. Выведите ответ по модулю $$$10^9 + 7$$$.

Формально, пусть $$$M = 10^9 + 7$$$. Можно показать, что ответ может быть представлен в виде несократимой дроби $$$\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^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 1023$$$).

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1,p_2,\ldots,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]$$$, и каждый элемент добавляется в $$$S$$$ с вероятностью $$$\frac{1}{2}$$$, поскольку $$$p_1 = p_2 = 5000$$$ и $$$\frac{p_i}{10^4} = \frac{1}{2}$$$. Поэтому есть всего $$$4$$$ возможных исхода для $$$S$$$, каждый из которых получается с вероятностью $$$\frac{1}{4}$$$:

  • $$$S = \varnothing$$$. В этом случае $$$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$$$.

Значит, ответ равен $$$0 \cdot \frac{1}{4} + 1 \cdot \frac{1}{4} + 4\cdot \frac{1}{4} + 9 \cdot \frac{1}{4} = \frac{14}{4} = \frac{7}{2} \equiv 500\,000\,007 \pmod{10^9 + 7}$$$.

Во втором наборе входных данных $$$a = [1, 1]$$$, $$$a_1$$$ добавляется в $$$S$$$ с вероятностью $$$0.1$$$, а $$$a_2$$$ добавляется в $$$S$$$ с вероятностью $$$0.2$$$. Есть всего $$$3$$$ исхода для $$$S$$$:

  • $$$S = \varnothing$$$. В этом случае $$$f(S) = 0$$$, $$$(f(S))^2 = 0$$$. Это происходит с вероятностью $$$(1-0.1) \cdot (1-0.2) = 0.72$$$.
  • $$$S = \{1\}$$$. В этом случае $$$f(S) = 1$$$, $$$(f(S))^2 = 1$$$. Это происходит с вероятностью $$$(1-0.1) \cdot 0.2 + 0.1 \cdot (1-0.2) = 0.26$$$.
  • $$$S = \{1, 1\}$$$. В этом случае $$$f(S) = 0$$$, $$$(f(S))^2 = 0$$$. Это происходит с вероятностью $$$0.1 \cdot 0.2 = 0.02$$$.

Значит, ответ равен $$$0 \cdot 0.72 + 1 \cdot 0.26 + 0 \cdot 0.02 = 0.26 = \frac{26}{100} \equiv 820\,000\,006 \pmod{10^9 + 7}$$$.