[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]$。