Expected Number of Connected Components

There are $N$ nodes, numbered with the distinct integers from 1 to $N$. You pick a random subset of these nodes. Node $i$ enters the subset with probability $P_i$, independently of every other node.

Two nodes in the subset are joined by an edge when the greatest common divisor of their numbers is larger than 1. Find the expected number of connected components of the resulting subgraph.

The first line has the number of test cases $T$ ($T \le 100$).

Each test case takes two lines. The first line has the number of nodes $N$ ($1 \le N \le 100$). The second line has $N$ real numbers separated by spaces. The $i$-th real number $P_i$ is the probability that node $i$ is in the subset ($0 \le P_i \le 1$, $1 \le i \le N$). Each real number is given with at most two digits after the decimal point.

For each test case, let $E$ be the expected number of connected components. Print $E \times 100^N$ modulo $1000000007$ on its own line. The value $E \times 100^N$ is always an integer.

The greatest common divisor of node 1 and any other node is 1, so node 1 always forms a component by itself when it is in the subset.

Take $N = 4$ with all four probabilities equal to $0.5$. Each of the 16 subsets appears with probability $0.0625$, and the component counts of those 16 subsets add up to 28. The expected value is $28 / 16 = 1.75$, so the value to print is $1.75 \times 100^4 = 175000000$.