Nora's Toy Boxes

SIHanatsuka - EMber

SIHanatsuka - ATONEMENT

Back in time, the seven-year-old Nora used to play lots of games with her creation ROBO_Head-02, both to have fun and enhance his abilities.

One day, Nora's adoptive father, Phoenix Wyle, brought Nora n boxes of toys. Before unpacking, Nora decided to make a fun game for ROBO.

She labelled all n boxes with n distinct integers a_1, a_2, …, a_n and asked ROBO to do the following action several (possibly zero) times:

• Pick three distinct indices i, j and k, such that a_i ∣ a_j and a_i ∣ a_k. In other words, a_i divides both a_j and a_k, that is a_j mod a_i = 0, a_k mod a_i = 0.
• After choosing, Nora will give the k-th box to ROBO, and he will place it on top of the box pile at his side. Initially, the pile is empty.
• After doing so, the box k becomes unavailable for any further actions.

Being amused after nine different tries of the game, Nora asked ROBO to calculate the number of possible different piles having the largest amount of boxes in them. Two piles are considered different if there exists a position where those two piles have different boxes.

Since ROBO was still in his infant stages, and Nora was still too young to concentrate for a long time, both fell asleep before finding the final answer. Can you help them?

As the number of such piles can be very large, you should print the answer modulo 10^9 + 7.

Input

The first line contains an integer n (3 ≤ n ≤ 60), denoting the number of boxes.

The second line contains n distinct integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 60), where a_i is the label of the i-th box.

Output

Print the number of distinct piles having the maximum number of boxes that ROBO_Head can have, modulo 10^9 + 7.

Examples

Input

3 2 6 8

Output

2

Input

5 2 3 4 9 12

Output

4

Input

4 5 7 2 9

Output

1

Note

Let's illustrate the box pile as a sequence b, with the pile's bottommost box being at the leftmost position.

In the first example, there are 2 distinct piles possible:

• b = [6] ([2, 6, 8] \xrightarrow{(1, 3, 2)} [2, 8])
• b = [8] ([2, 6, 8] \xrightarrow{(1, 2, 3)} [2, 6])

In the second example, there are 4 distinct piles possible:

• b = [9, 12] ([2, 3, 4, 9, 12] \xrightarrow{(2, 5, 4)} [2, 3, 4, 12] \xrightarrow{(1, 3, 4)} [2, 3, 4])
• b = [4, 12] ([2, 3, 4, 9, 12] \xrightarrow{(1, 5, 3)} [2, 3, 9, 12] \xrightarrow{(2, 3, 4)} [2, 3, 9])
• b = [4, 9] ([2, 3, 4, 9, 12] \xrightarrow{(1, 5, 3)} [2, 3, 9, 12] \xrightarrow{(2, 4, 3)} [2, 3, 12])
• b = [9, 4] ([2, 3, 4, 9, 12] \xrightarrow{(2, 5, 4)} [2, 3, 4, 12] \xrightarrow{(1, 4, 3)} [2, 3, 12])

In the third sequence, ROBO can do nothing at all. Therefore, there is only 1 valid pile, and that pile is empty.

inputFormat

Input

The first line contains an integer n (3 ≤ n ≤ 60), denoting the number of boxes.

The second line contains n distinct integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 60), where a_i is the label of the i-th box.

outputFormat

Output

Print the number of distinct piles having the maximum number of boxes that ROBO_Head can have, modulo 10^9 + 7.

Examples

Input

3 2 6 8

Output

2

Input

5 2 3 4 9 12

Output

4

Input

4 5 7 2 9

Output

1

Note

Let's illustrate the box pile as a sequence b, with the pile's bottommost box being at the leftmost position.

In the first example, there are 2 distinct piles possible:

• b = [6] ([2, 6, 8] \xrightarrow{(1, 3, 2)} [2, 8])
• b = [8] ([2, 6, 8] \xrightarrow{(1, 2, 3)} [2, 6])

In the second example, there are 4 distinct piles possible:

• b = [9, 12] ([2, 3, 4, 9, 12] \xrightarrow{(2, 5, 4)} [2, 3, 4, 12] \xrightarrow{(1, 3, 4)} [2, 3, 4])
• b = [4, 12] ([2, 3, 4, 9, 12] \xrightarrow{(1, 5, 3)} [2, 3, 9, 12] \xrightarrow{(2, 3, 4)} [2, 3, 9])
• b = [4, 9] ([2, 3, 4, 9, 12] \xrightarrow{(1, 5, 3)} [2, 3, 9, 12] \xrightarrow{(2, 4, 3)} [2, 3, 12])
• b = [9, 4] ([2, 3, 4, 9, 12] \xrightarrow{(2, 5, 4)} [2, 3, 4, 12] \xrightarrow{(1, 4, 3)} [2, 3, 12])

In the third sequence, ROBO can do nothing at all. Therefore, there is only 1 valid pile, and that pile is empty.

样例

4
5 7 2 9

1

</p>