← 返回题目列表

Codeforces · 1292/F

F. 诺拉的玩具盒

中文机器翻译题面 查看原题

回到过去,七岁的诺拉经常和她的创造物 ROBO_Head-02 一起玩很多游戏,既可以享受乐趣,也可以增强他的能力。

有一天,诺拉的养父菲尼克斯·怀尔给诺拉带来了 $$$n$$$ 盒玩具。在开箱之前,Nora 决定为 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,他将其放在他身边的盒子堆的顶部。最初,堆是空的。
- 执行此操作后,$$$k$$$ 框将无法执行任何进一步操作。

经过九次不同的游戏尝试后,诺拉感到很有趣,她要求 ROBO 计算其中盒子数量最多的可能不同堆的数量。如果存在两个桩具有不同盒子的位置,则认为这两桩是不同的。

由于ROBO还处于婴儿期,而诺拉还太小,无法长时间集中注意力,所以在找到最终答案之前,两人都睡着了。你能帮助他们吗?

由于此类堆的数量可能非常大,因此您应该打印对 $$$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$$$ 为模。

示例

输入 #1

3
2 6 8

输出 #1

2

输入 #2

5
2 3 4 9 12

输出 #2

4

输入 #3

4
5 7 2 9

输出 #3

1

注意

让我们将盒子堆说明为序列 $$$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$$$ 有效堆,并且该堆是空的。