给定一个包含 $n$ 个整数的序列 $a_1, a_2, \dots, a_n$。我们用它构造一个具有 $n$ 个顶点的无向图：顶点 $i$ 和 $j$（其中 $i \neq j$）之间由 $\text{NWD}(a_i, a_j)$ 条不同的边相连。你的任务是计算该图中生成树的数量。如果两棵树包含的边集不同，则认为它们是不同的。由于该数量可能非常大，你只需输出其对 $10^9 + 7$ 取模后的结果。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 5\,000$)，表示序列的长度，同时也表示图的顶点数。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 5\,000$)，即题目描述中提到的序列。
输出格式
输出一行一个整数，表示该图中不同生成树的数量对 $10^9 + 7$ 取模后的结果。
样例
输入 1
4 1 2 3 4
输出 1
24
说明 1
样例中的图结构如下：
样例解释：图结构示意图
容易计算得出，该图包含恰好 24 棵不同的生成树。