E-min25筛_牛客小白月赛109

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

题目描述

$\hspace{15pt}$ 因为 Onewan 在 gdcpc 和昆明区域赛都没有写出 min25筛 所以他不喜欢 $25$ 这个数字。

$\hspace{15pt}$ 现在，对于给定的由 $n$ 个元素组成的数组 $\{a_1, a_2, \dots, a_n\}$ ，记 $\displaystyle S(i,j)=\prod_{k=i}^{j} a_k = a_i \times a_{i+1} \times \dots \times a_j$ ；记 $F(i,j)$ 由以下伪代码得出：
$\begin{aligned} &F(i,j) \gets S(i,j) \\ &\textbf{while}\ F(i,j) \bmod 25 = 0\ \textbf{do} \\ &\qquad F(i,j) \gets F(i,j) \div 25 \\ &\textbf{end while} \end{aligned}$
$\hspace{15pt}$ 询问 $\displaystyle \sum\limits_{i=1}^{n}\sum\limits_{j=i}^{n} F(i,j)$ 。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

输入描述:

第一行输入一个整数  代表数组中的元素数量。
第二行输入  个整数  代表数组中的元素。

输出描述:

在一行上输出一个整数，代表  。由于答案可能很大，请将答案对  取模后输出。

示例1

输入

复制

5
1 2 3 4 5

输出

复制

示例2

输入

复制

10
5 10 15 25 30 45 55 6 100 5

输出

复制