연결 요소 개수의 기댓값

각 정점 i가 확률 P_i로 선택될 때, gcd가 1보다 큰 두 선택 정점을 연결한 부분그래프의 연결 요소 개수의 기댓값을 구하고 E × 100^N을 1e9+7로 나눈 나머지를 출력한다.

어려움8확률수학정수론유니온 파인드아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제 설명

예제3

문제

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$ 이다.