题目背景

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

题目描述

小宋有一个序列 $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$，表示答案。

2
5 5

4

4
1 1 4 5

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