【问题描述】

给定 $n$ 和长度为 $n$ 的正整数序列 $a$。
定义一次操作为，选择一个数 $a_i$ 和质数 $p$，将 $a_i$ 赋值为 $a_i\times p$ 或 $\frac{a_i}{p}$，必须满足赋值后 $a_i$ 为正整数。
定义区间 $l,r$ 的代价 $val(l,r)$ 为，使 $a_l,a_{l+1},\cdots,a_r$ 全都相等的最小操作次数。

请求出 $\sum_{l=1}^n \sum_{r=l}^n val(l,r)$，对 $10^9+7$ 取模。

【输入格式】

第一行一个数 $n$。
第二行 $n$ 个，表示序列 $a$。

【输出格式】

输出一行一个整数表示答案。

【样例输入1】

2
2 4

【样例输出1】

1

【样例输入2】

3
63 28 56

【样例输出2】

10

【样例输入3】

10
1 2 3 4 5 6 7 8 9 10

【样例输出3】

319

【样例4】

见下发文件，该样例满足测试点 $12,13$ 的限制。

【样例5】

见下发文件，该样例满足测试点 $19,20$ 的限制。

【数据范围及约定】

对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$，$1\le a_i\le 10^6$。