LCM Tree

Time limit2sMemory limit512 MB

Summary

Count the ways to arrange n given values into a full binary tree where each parent value is the LCM of its two children, modulo 1e9+7.

Level: Medium7 of 10
Topics: Dynamic programming, Bit manipulation, Number theory
Solved: No attempts yet

Problem

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. In how many ways can they be arranged into an LCM tree, modulo $10^9 + 7$ ? 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. 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 \le n \le 25$ ). The second line has $n$ positive integers, each 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$ .

Examples4

Example 1
Input
```
7
2 3 4 4 8 12 24
```
Expected output
```
2
```
Example 2
Input
```
3
7 7 7
```
Expected output
```
3
```
Example 3
Input
```
5
1 2 3 2 1
```
Expected output
```
0
```
Example 4
Input
```
13
1 1 1 1 1 1 1 1 1 1 1 1 1
```
Expected output
```
843230316
```