Дан массив, состоящий из \(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}\).
Выходные данные
Для каждого набора входных данных выведите математическое ожидание \((f(S))^2\) по модулю \(10^9 + 7\).
Примечание
В первом наборе входных данных \(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}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|