Counting Trailing 5's in Subarrays

You are given a sequence \(a_1, a_2, \dots, a_n\) where each \(a_i\) is a digit between 0 and 9. For any subarray defined by indices \(l\) and \(r\) (with \(1 \le l \le r \le n\)), define \(f(l,r)\) as the number of consecutive trailing \(5\)'s in the number formed by concatenating \(a_l a_{l+1} \dots a_r\). For example, given the sequence \(a = \{1, 1, 4, 5, 1, 4\}\), we have \(f(2,4)=1\) and \(f(1,3)=0\).

Your task is to calculate and output the value of

[ S = \left(\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)\right) \bmod (10^9+7) ]

Be sure to use efficient methods as the total number of subarrays is large.

inputFormat

The first line contains an integer \(n\) which denotes the length of the sequence.

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) where each \(a_i \in [0,9]\).

outputFormat

Output a single integer, the value of \(S\) modulo \(10^9+7\).

sample

6
1 1 4 5 1 4

4