P9710 [KMOI R1] Five Five Five Five (Easy)

“Numbers in slow order are not born from the supernatural. They have a form that can be checked, and a quantity that can be inferred.” — Zu Chongzhi.

Xiao Song has a sequence $a_1,a_2\dots,a_n$. For $i\in [1,n]$, it satisfies $a_i\in[0,9]$. For $1\le l\le r\le n$, he defines $f(l,r)$ as the number of consecutive trailing $5$’s at the end of $\overline{a_la_{(l+1)}\dots a_r}$. For example, for the sequence $a=\{1,1,4,5,1,4\}$, we have $f(2,4)=1$ and $f(1,3)=0$. Now please compute: $$\Big(\sum\limits_{l=1}^ {n}\sum\limits_{r=l}^{n} f(l,r)\Big) \bmod 10^9+7$$

The first line contains a positive integer $n$, representing the length of the sequence. The second line contains $n$ integers $a_1,a_2,\dots,a_n$, representing the sequence $a$.

One positive integer $ans$, representing the answer.

## Explanation for Sample $1$: $f(1,1)=1$. $f(1,2)=2$. $f(2,2)=1$. So the answer is $ans=f(1,1)+f(1,2)+f(2,2)=4$, therefore output $4$. ## Constraints **This problem uses bundled subtask testdata.** Let $m=\max\{a_1,a_2,\dots,a_n\}$. | Subtask ID | Test Point ID | $n\le$ | $m\le$ | Special Property | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $1$ | $100$ | $3$ | None | $3$ | | $2$ | $2\sim 4$ | $2\times 10^5$ | $5$ | $\mathbf{A}$ | $22$ | | $3$ | $5,6$ | $100$ | $5$ | None | $10$ | | $4$ | $7\sim 10$ | $2\times 10^5$ | $5$ | $\mathbf{B}$ | $25$ | | $5$ | $11\sim 20$ | $2\times 10^5$ | $9$ | None | $40$ | Special property $\mathbf{A}:$ The average of the sequence is $5$. Special property $\mathbf{B}:$ The sequence is monotone non-increasing. For $100\%$ of the data: $1\le n\le 2\times 10^5$, $0\le m\le 9$. For $\forall i\in [1,n]$, it holds that $a_i\in[0,9]$. Translated by ChatGPT 5