Codeforces Round 614 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

combinatorics

dp

*3500

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Nora's Toy Boxes

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBack 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, \ldots, 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 \mid a_j$$$ and $$$a_i \mid a_k$$$. In other words, $$$a_i$$$ divides both $$$a_j$$$ and $$$a_k$$$, that is $$$a_j \bmod a_i = 0$$$, $$$a_k \bmod 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 \le n \le 60$$$), denoting the number of boxes.

The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 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, \mathbf{6}, 8] \xrightarrow{(1, 3, 2)} [2, 8]$$$)
- $$$b = [8]$$$ ($$$[2, 6, \mathbf{8}] \xrightarrow{(1, 2, 3)} [2, 6]$$$)

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

- $$$b = [9, 12]$$$ ($$$[2, 3, 4, \mathbf{9}, 12] \xrightarrow{(2, 5, 4)} [2, 3, 4, \mathbf{12}] \xrightarrow{(1, 3, 4)} [2, 3, 4]$$$)
- $$$b = [4, 12]$$$ ($$$[2, 3, \mathbf{4}, 9, 12] \xrightarrow{(1, 5, 3)} [2, 3, 9, \mathbf{12}] \xrightarrow{(2, 3, 4)} [2, 3, 9]$$$)
- $$$b = [4, 9]$$$ ($$$[2, 3, \mathbf{4}, 9, 12] \xrightarrow{(1, 5, 3)} [2, 3, \mathbf{9}, 12] \xrightarrow{(2, 4, 3)} [2, 3, 12]$$$)
- $$$b = [9, 4]$$$ ($$$[2, 3, 4, \mathbf{9}, 12] \xrightarrow{(2, 5, 4)} [2, 3, \mathbf{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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/10/2023 21:24:01 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|