[KMOI R1] 五五五五(Easy)

题目背景

“迟序之数,非出神怪,有形可检,有数可推。”——祖冲之

题目描述

小宋有一个序列 $a_1,a_2\dots,a_n$,其中对于 $i\in [1,n]$,满足 $a_i\in[0,9]$。 对于 $1\le l\le r\le n$,他记 $f(l,r)$ 等于 $\overline{a_la_{(l+1)}\dots a_r}$ 的末尾连续 $5$ 的个数。 例如:对于序列 $a=\{1,1,4,5,1,4\}$,$f(2,4)=1,f(1,3)=0$。 现在请你求出: $$\Big(\sum\limits_{l=1}^ {n}\sum\limits_{r=l}^{n} f(l,r)\Big) \bmod 10^9+7$$

输入输出格式

输入格式


第一行一个正整数 $n$,表示序列的长度。 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$,表示序列 $a$。

输出格式


一个正整数 $ans$,表示答案。

输入输出样例

输入样例 #1

2
5 5

输出样例 #1

4

输入样例 #2

4
1 1 4 5

输出样例 #2

4

说明

## 样例 $1$ 解释: $f(1,1)=1$。 $f(1,2)=2$。 $f(2,2)=1$。 得到答案 $ans=f(1,1)+f(1,2)+f(2,2)=4$,故输出 $4$。 ## 数据范围 **本题采用 subtask 捆绑测试。** 令 $m=\max\{a_1,a_2,\dots,a_n\}$。 | 子任务编号 | 测试点编号 | $n\le$ | $m\le$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $1$ | $100$ | $3$ | 无 | $3$ | | $2$ | $2\sim 4$ | $2\times 10^5$ | $5$ | $\mathbf{A}$ | $22$ | | $3$ | $5,6$ | $100$ | $5$ | 无 | $10$ | | $4$ | $7\sim 10$ | $2\times 10^5$ | $5$ | $\mathbf{B}$ | $25$ | | $5$ | $11\sim 20$ | $2\times 10^5$ | $9$ | 无 | $40$ | 特殊性质 $\mathbf{A}:$ 序列平均数为 $5$。 特殊性质 $\mathbf{B}:$ 序列单调不上升。 对于 $100\%$ 的数据:$1\le n\le 2\times 10^5$,$0\le m\le 9$。 对于 $\forall i\in [1,n]$,满足 $a_i\in[0,9]$。