연결 요소 개수의 기댓값

1부터 $N$까지 서로 다른 정수로 번호가 붙은 노드 $N$개가 있다. 이 노드 중 일부를 무작위로 골라 부분집합을 만든다. 노드 $i$가 부분집합에 들어갈 확률은 $P_i$이고, 노드마다 독립이다.

부분집합에 속한 두 노드는 번호의 최대공약수가 1보다 클 때 간선으로 이어진다. 이렇게 만들어진 부분 그래프의 연결 요소 개수의 기댓값을 구하라.

첫째 줄에 테스트 케이스 개수 $T$가 주어진다 ($T \le 100$).

각 테스트 케이스는 두 줄이다. 첫째 줄에 노드 개수 $N$이 주어진다 ($1 \le N \le 100$). 둘째 줄에 실수 $N$개가 공백으로 구분되어 주어진다. $i$번째 실수 $P_i$는 노드 $i$가 부분집합에 포함될 확률이다 ($0 \le P_i \le 1$, $1 \le i \le N$). 각 실수는 소수점 아래 두 자리까지 주어진다.

각 테스트 케이스마다 연결 요소 개수의 기댓값 $E$를 구해서 $E \times 100^N$을 $1000000007$로 나눈 나머지를 한 줄에 출력한다. $E \times 100^N$은 항상 정수다.

노드 1은 다른 어떤 노드와도 최대공약수가 1이므로 부분집합에 들어가면 항상 혼자 연결 요소 하나를 이룬다.

$N = 4$이고 네 확률이 모두 $0.5$인 경우를 보자. 부분집합 16개가 각각 확률 $0.0625$로 나오고, 이 16가지의 연결 요소 개수를 모두 더하면 28이다. 따라서 기댓값은 $28 / 16 = 1.75$이고, 출력할 값은 $1.75 \times 100^4 = 175000000$이다.