Celestial Resort

题号：NC207703
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Madeline来到了Celeste山的天空度假山庄（Celestial Resort）。工作人员Oshiro先生希望Madeline住在这里，而这里却因为早就没有客人来光顾而脏乱不堪。

虽然Madeline不想留在这里，她的目标是登上Celeste山，但她不忍心看到Oshiro先生失落的样子，于是想要帮助Oshiro先生来整理天空度假山庄。

Madeline发现这里有 ${n}$ 种书，每一种书都有无限本，第 ${i}$ 种书的厚度是 $a_i$ ，她想把这 ${n}$ 种书在摆成一排，每一种书叠 $b_i$ 本，使得每一种书叠起来的高度相同。( $b_i \ge 1$ ) 即所有 $1\le i,j\le n, a_i\cdot b_i = a_j\cdot b_j$ 她想知道 $\sum\limits_{i=1}^{n}{b_i}$ 的最小值是多少。

比如当前有 ${3}$ 种书，这三本书的厚度分别为 ${2}$ 、 ${3}$ 、 ${4}$ ，那么这三本书各自需要 ${6}$ 、 ${4}$ 、 ${3}$ 本书可以使得每一种书叠起来的高度相同，那么总共需要 ${13}$ 本。可以证明这种情况下需要的书的总数是最少的。

这个结果可能会很大，求结果对 $10^{9}+7$ 取模的结果。

输入描述:

只有一组输入数据。
第一行输入一个数，代表书的种类数。（）
第二行输入个整数，代表第本书的高度。（）

输出描述:

输出的最小值对取模的结果。

示例1

输入

复制

3
1000000 999999 999998

输出

复制

996989508