LCM Tree
시간 제한2초메모리 제한512 MB
주어진 n개의 양의 정수를 각 내부 노드의 값이 두 자식 값의 최소공배수인 이진 LCM 트리로 배치하는 경우의 수를 1e9+7로 나눈 나머지로 구한다.
문제
An LCM tree is a binary tree in which each node has a positive integer value, and either zero or two children. If two nodes x and y are the children of node z, then the Least Common Multiple (LCM) of the values of node x and node y must equal the value of node z.
You are given n nodes with positive integer values to be arranged into an LCM tree. In how many ways (modulo 109 + 7) can you do that? Two ways are considered different if there are two nodes x and y so that x is a child of y in one way but not in the other way.
The illustration shows one of the two ways for the first sample case. The other way can be obtained by swapping the two nodes with value 4. Note that swapping the two leaves with values 2 and 4 does not give a different way.
입력
The first line has an odd integer n (1 ≤ n ≤ 25). The second line has n positive integers no larger than 109, giving the values of the nodes.
출력
Output the number of ways to arrange the given nodes into an LCM tree, modulo 109 + 7.