問題文

整数 $N$ 、長さ $N$ の整数列 $A$ 、英小文字からなる長さ $N$ の文字列 $S$ が与えられます。

文字列 $T$ は空文字列から始まって、 $i=1,2,...,N$ の順に、末尾に $S$ の $i$ 文字目を $A_{i}$ 回加えたものです。

つまり、文字列 $T$ は長さ $\sum_{i=1}^{N}A_i$ の文字列で、任意の $i$ に対して以下が成り立ちます。

• $(1+\sum_{k=1}^{i-1}A_k)$ 文字目から $(\sum_{k=1}^{i}A_k)$ 文字目は $S$ の $i$ 文字目と同じである。

ここで、文字列 $T$ に対して $T_i$ を $T$ の $i$ 文字目以降からなる文字列とし、 $f(i)$ を $T$ と $T_i$ を先頭から見て一致している文字数 (最長共通接頭辞の長さ) とします。

$\sum_{i=1}^{|T|}f(i)$ を $(10^{9}+7)$ で割ったあまりを求めてください。

制約

• $1\leq N \leq 2\times 10^5$
• $1\leq A_{i} \leq 10^{9}\ (1\leq i \leq N)$
• $N$ 及び $A$ の要素は全て整数
• $S$ は英小文字のみからなる長さ $N$ の文字列
• $1 \leq i\leq N-1$において、$S_i\neq S_{i+1}$

入力

$N$
$ A_1 \; A_2 \; ...\;A_N$
$S$

出力

答えを $(10^{9}+7)$ で割ったあまりを出力してください。 最後に改行してください。

サンプル

2
2 2
ab

5

1
27
k

378

6
1 22 333 4444 55555 666666
tomato

782598