Background

“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.

Problem Description

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$$

Input Format

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$.

Output Format

One positive integer $ans$, representing the answer.

2
5 5

4

4
1 1 4 5

4

Hint

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$		$100$	$3$	None	$3$
$2$	$2\sim 4$	$2\times 10^5$	$5$	$\mathbf{A}$	$22$
$3$	$5,6$	$100$		None	$10$
$4$	$7\sim 10$	$2\times 10^5$		$\mathbf{B}$	$25$
$5$	$11\sim 20$		$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