小红的序列乘积2.0
题号：NC276158
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

\,\,\,\,\,\,\,\,\,\,对于一个长度为 m 的整数序列 \{b_1,b_2,\dots,b_m\}，定义 f_i = b_1 \times b_2 \times \cdots \times b_i ，即前 i 项的乘积。这个序列的权值即为 f_1, f_2, \dots, f_m 中个位数是 6 的数字个数。
\,\,\,\,\,\,\,\,\,\,小红有一个长度为 n 的整数序列 \{a_1,a_2,\dots,a_n\}，她想知道这个序列全部 2^n-1 个非空子序列的权值和是多少。

\,\,\,\,\,\,\,\,\,\,如果序列 a 可以通过删除序列 b 中的若干（可能为零或全部）元素得到，则序列 a 是序列 b 的子序列。

输入描述:

\,\,\,\,\,\,\,\,\,\,第一行输入一个整数 n \left(1 \leq n \leq 10^5\right) 代表序列中元素的数量。
\,\,\,\,\,\,\,\,\,\,第二行输入 n 个整数 a_1, a_2, \cdots, a_n \left(1 \leq a_i \leq 10^9\right) 代表序列元素。

输出描述:

\,\,\,\,\,\,\,\,\,\,在一行上输出一个整数，输出一个整数，表示全部子序列的权值和。由于答案可能很大，请将答案对 (10^9+7) 取模后输出。
示例1

输入

复制 
3
4 4 6

输出

复制 
4

说明

\,\,\,\,\,\,\,\,\,\,对于子序列 [4] ，没有贡献；
\,\,\,\,\,\,\,\,\,\,对于子序列 [6] ，f=\{6\} 贡献为 1 ；
\,\,\,\,\,\,\,\,\,\,对于子序列 [4,4] ，f=\{4,16\} 贡献为 1 ；
\,\,\,\,\,\,\,\,\,\,对于子序列 [4,6] ，f=\{4,24\} ，没有贡献；
\,\,\,\,\,\,\,\,\,\,对于子序列 [4,4,6] ，f=\{4,16,96\} 贡献为 2 。
示例2

输入

复制 
5
1 2 3 4 4

输出

复制 
12