F. Игрушки Норы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
SIHanatsuka - EMber
SIHanatsuka - ATONEMENT

Давным давно, семилетняя Нора любила играть в игрушки вместе со своим созданием ROBO_Head-02, не только для того чтобы развлечься, но и чтобы улучшить его способности.

Однажды, приёмный отец Норы, Феникс Уайл, принёс Норе $$$n$$$ коробок с игрушками. Перед тем как их распаковать, Нора решила устроить для ROBO небольшую игру.

Она пронумеровала все $$$n$$$ коробок используя $$$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$$$.
  • Затем, Нора передаст $$$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, по модулю $$$10^9 + 7$$$.

Примеры
Входные данные
3
2 6 8
Выходные данные
2
Входные данные
5
2 3 4 9 12
Выходные данные
4
Входные данные
4
5 7 2 9
Выходные данные
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$$$ стопка, и это пустая стопка.