Long Continuous Substrings

2 secs 1024 MB
Nachia's icon Nachia

出典

potato167 さんの出題 yukicoder No.1845 Long Substrings に対する tatyam さんの改題

問題文

整数 NN 、長さ NN の整数列 AA 、英小文字からなる長さ NN の文字列 SS が与えられます。

文字列 TT は空文字列から始まって、 i=1,2,,Ni=1,2, \ldots ,N の順に、末尾に SSii 文字目を AiA_i 回加えたものです。

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

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

文字列 TT の空でない部分文字列としてありうる文字列は何通りあるか求めてください。 また、答えは非常に大きくなることがあるので、(109+7)(10^9+7) で割ったあまりを出力してください。

文字列 XX の部分文字列とは、文字列 XX の先頭または末尾からそれぞれ 00 文字以上取り除いて得られる文字列のことです。

制約

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1Ai1091 \leq A_i \leq 10^9 (1iN)(1 \leq i \leq N)
  • NN および AA の要素はすべて整数
  • SS は英小文字のみからなる長さ NN の文字列
  • SiSi+1S_i \neq S_{i+1} (1iN1)(1 \leq i \leq N-1)

入力

NN
A1A_1 A2A_2 \ldots ANA_N
SS

出力

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

入出力例

サンプル1

2
2 2
ab
8

T=T={} aabb であり、 TT の空でない部分文字列としてあり得るのは、 a, aa, aab, aabb, ab, abb, b, bb88 通りであるので、 88 を出力します。

サンプル2

3
1 1 1
ioi
5

T=T={} ioi であり、 TT の空でない部分文字列としてあり得るのは、 i, io, ioi, o, oi55 通りであるので、 55 を出力します。

サンプル3

6
1 22 333 4444 55555 666666
potato
505606561

サンプル4

9
123456 23456 3456 123456 23456 3456 123456 23456 3456
atoatoato
624732688

Submit


Go (1.21)