LCM 트리

시간 제한2초메모리 제한512 MB

요약

주어진 n개의 값을 각 부모 노드의 값이 두 자식 값의 최소공배수가 되는 이진 트리로 배치하는 경우의 수를 10^9+7로 나눈 나머지로 구합니다.

문제

LCM 트리는 각 노드가 양의 정수 값을 하나 갖고, 자식을 0개 또는 2개 가지는 이진 트리이다. 노드 z의 자식이 노드 x와 y라면, 노드 x의 값과 노드 y의 값의 최소공배수(LCM)는 노드 z의 값과 같아야 한다.

양의 정수 값을 가진 노드 $n$ 개를 LCM 트리로 배열하는 방법이 몇 가지인지 $10^9 + 7$ 로 나눈 나머지를 구하시오. 두 배열은 어떤 노드 x와 y에 대해 한쪽에서는 x가 y의 자식이고 다른 쪽에서는 그렇지 않다면 서로 다른 배열이다.

그림은 첫 번째 예제의 두 가지 배열 중 하나를 보여준다. 값이 4인 두 노드를 서로 바꾸면 나머지 배열이 된다. 값이 2와 4인 두 잎 노드를 바꾸는 것은 다른 배열을 만들지 않는다.

첫 줄에 홀수인 정수 $n$ ( $1 \le n \le 25$ )이 주어진다. 둘째 줄에는 노드의 값을 나타내는 양의 정수 $n$ 개가 주어지며, 각 값은 $10^9$ 이하이다.

주어진 노드들을 LCM 트리로 배열하는 방법의 수를 $10^9 + 7$ 로 나눈 나머지를 출력한다.