CF1292F.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, \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$.

SIHanatsuka - EMber

SIHanatsuka - ATONEMENT

时光倒流，七岁的诺拉曾经常与她创造的机器人 ROBO_Head-02 一起玩各种游戏，既为了娱乐，也为了提升他的能力。

某天，诺拉的养父菲尼克斯·怀尔（Phoenix Wyle）给诺拉带来了 $n$ 盒玩具。在拆箱之前，诺拉决定为 ROBO 设计一个有趣的游戏。

她用 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$ 给所有 $n$ 个盒子分别贴上标签，并要求 ROBO 执行以下操作若干次（次数可以为零）：

• 选出三个互不相同的下标 $i$、$j$ 和 $k$，满足 $a_i \mid a_j$ 且 $a_i \mid a_k$。换言之，$a_i$ 同时整除 $a_j$ 和 $a_k$，即 $a_j \bmod a_i = 0$，$a_k \bmod a_i = 0$。
• 选定后，诺拉会将第 $k$ 个盒子交给 ROBO，ROBO 将其放置于自己身旁的盒子堆的最上方。初始时，该堆为空。
• 完成此操作后，第 $k$ 个盒子即变为不可再使用的状态。

在尝试了九种不同的玩法并感到十分有趣之后，诺拉让 ROBO 计算：所有可能的、包含最多盒子数的堆中，互不相同的堆的总数。若两个堆在某个位置上所含盒子不同，则认为这两个堆互不相同。

由于此时 ROBO 仍处于“婴儿期”，而诺拉也尚且年幼，难以长时间集中注意力，因此两人在得出最终答案前便都睡着了。你能帮他们解答这个问题吗？

由于满足条件的堆的数量可能非常大，请输出答案对 $10^9 + 7$ 取模的结果。

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.

第一行包含一个整数 $n$（$3 \le n \le 60$），表示盒子的数量。

第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 60$），其中 $a_i$ 表示第 $i$ 个盒子的标签。

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

输出 ROBO_Head 能拥有的、箱子数量最多的不同堆叠方式的数量，结果对 $10^9 + 7$ 取模。

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.

我们将箱子堆叠表示为一个序列 $b$，其中堆叠最底部的箱子位于最左侧位置。

在第一个例子中，共有 $2$ 种不同的堆叠方式：

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

在第二个例子中，共有 $4$ 种不同的堆叠方式：

• $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]$）

在第三个序列中，ROBO 完全无法进行任何操作。因此，仅存在 $1$ 种合法的堆叠方式，且该堆叠为空。