### 问题描述 小明最近在了解了回文串后对回文串表现出了非常大的兴趣，尤其是对于 “aba” 这个回文串，此时，小红为了满足（打击）小明的热情，给小明出了一道题目： 给定一个长度为 $n$ 的数组 $a$ ，和一个长度同为 $n$ 的字符串 $s$ （下标均从 $1$ 开始）。要求小明在字符串 $s$ 中找到所有等于 “aba” 的子串 （不要求连续），并把与子串下标相同的 $a$ 数组中的值求和，并将结果对 $10^9+7$ 求余。 例如： $a = [1,3,2,5,4]$ ，$s=$ “abcda” ，此时， $s$ 中与 “aba” 相等的字串下标为 $[1,2,5]$ ，对应数组 $a$ 中的值分别为 $[1,3,4]$ ，求和后值为 $8$ 。 小明为了表达自己对 “aba” 的喜爱，决定要在 $1$ 内求出答案，你能帮帮他吗？ ### 输入格式 第一行，一个正整数 $n$ $(3\leq n\leq 10^6)$ ，代表数组和字符串的长度。 第二行，包含 $n$ 个正整数，代表 $a_i$ $(1\leq i\leq n , 1\leq a_i\leq10^9)$ 。 第三行，包含一个字符串 $s$ ，代表小红给出的字符串 $s$ 。 ### 输出格式 一行，包含一个正整数，代表小明应该给出的结果对 $10^9+7$ 求余后的答案。 ### 样例输入 1 ``` 5 1 3 2 5 4 abcda ``` ### 样例输出 1 ``` 8 ``` ### 样例输入 2 ``` 5 1 2 3 4 5 ababa ``` ### 样例输出 2 ``` 36 ``` ### 样例说明 样例 $1$ ：见问题描述。 样例 $2$ ： 在字符串 $s$ 中，等于 “aba” 的字串下标有 ： $[1,2,3]$ ， $[1,2,5]$ ， $[1,4,5]$ ， $[3,4,5]$ 。对应数组 $a$ 中的值的和分别为：$1+2+3=6$ ， $1+2+5=8$ ， $1+4+5=10$ ， $3+4+5=12$ ，总和为： $6+8+10+12=36$ 。所以小明应该给出的答案是 $36$ 。