You are given a sequence of $n$ integers $a_1, a_2, \dots, a_n$. Using this sequence, we construct an undirected graph with $n$ vertices: vertices $i$ and $j$ (for $i \neq j$) are connected by $\gcd(a_i, a_j)$ distinct edges. Your task is to calculate the number of spanning trees in the given graph. Two spanning trees are considered different if one of them contains an edge that the other does not. Since this number can be very large, it is sufficient to provide its remainder when divided by $10^9 + 7$.

Input

The first line of standard input contains a single integer $n$ ($1 \le n \le 5\,000$), representing the length of the sequence and the number of vertices in the graph.

The second line of standard input contains a sequence of $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 5\,000$), as described in the problem statement.

Output

The only line of standard output should contain a single integer representing the remainder when the number of different spanning trees of the described graph is divided by $10^9 + 7$.

Examples

Input 1

4
1 2 3 4

Output 1

24

Note

The graph in the example test case looks as follows:

It is easy to calculate that it contains exactly 24 different spanning trees.