CF1292F Nora's Toy Boxes

[SIHanatsuka - EMber](https://soundcloud.com/hanatsuka/sihanatsuka-ember) [SIHanatsuka - ATONEMENT](https://soundcloud.com/hanatsuka/sihanatsuka-atonement) 很久以前，七岁的 Nora 经常和她创造的 ROBO\_Head-02 玩各种游戏，既为了娱乐，也为了提升他的能力。 有一天，Nora 的养父 Phoenix Wyle 给 Nora 带来了 $n$ 个玩具盒。在拆开之前，Nora 决定为 ROBO 设计一个有趣的游戏。 她用 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_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$。 - 选择后，Nora 会把第 $k$ 个盒子交给 ROBO，ROBO 会把它放到自己身边的盒子堆顶端。最初，堆是空的。 - 这样做之后，第 $k$ 个盒子将不再参与后续操作。 在玩了九次不同的游戏后，Nora 让 ROBO 计算能获得最多盒子的不同盒子堆的数量。如果存在某个位置，两个堆上的盒子不同，则认为这两个堆不同。 由于 ROBO 还处于初级阶段，Nora 也太小无法长时间集中注意力，两人都在找到最终答案前睡着了。你能帮他们完成这个任务吗？ 由于可能的堆数量非常大，你需要输出答案对 $10^9 + 7$ 取模后的结果。

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

输出 ROBO\_Head 能获得的最多盒子的不同盒子堆的数量，结果对 $10^9 + 7$ 取模。

我们可以将盒子堆表示为一个序列 $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$ 个有效的盒子堆，即空堆。 由 ChatGPT 4.1 翻译