Problem F
LCM Tree
You are given $n$ nodes with positive integer values to be arranged into an LCM tree. In how many ways (modulo $10^9 + 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.
Input
The first line has an odd integer $n$ ($1 \leq n \leq 25$). The second line has $n$ positive integers no larger than $10^9$, giving the values of the nodes.
Output
Output the number of ways to arrange the given nodes into an LCM tree, modulo $10^9 + 7$.
| Sample Input 1 | Sample Output 1 |
|---|---|
7 2 3 4 4 8 12 24 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 7 7 7 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 1 2 3 2 1 |
0 |
| Sample Input 4 | Sample Output 4 |
|---|---|
13 1 1 1 1 1 1 1 1 1 1 1 1 1 |
843230316 |
