問題文

整数 $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$ の空でない部分列としてありうる文字列は何通りあるか求めてください。 また、答えは非常に大きくなることがあるので、$({10}^9+7)$ で割ったあまりを出力してください。

制約

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

入力

$N$
$A_1{A}_2...A_N$
$S$

出力

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

サンプル

2
2 2
ab

8

3
1 1 1
ioi

6

1
27
k

27

6
1 22 333 4444 55555 666666
potato

606835344