Long Continuous Substrings

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

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

文字列 は空文字列から始まって、 の順に、末尾に の 文字目を 回加えたものです。

つまり、文字列 は長さ の文字列で、任意の に対して以下が成り立ちます。

• 文字目から 文字目は の 文字目と同じである。

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

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

• および の要素はすべて整数
• は英小文字のみからなる長さ の文字列

答えを で割ったあまりを出力してください。 最後に改行してください。

2
2 2
ab

8

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

3
1 1 1
ioi

5

ioi であり、 の空でない部分文字列としてあり得るのは、 i, io, ioi, o, oi の 通りであるので、 を出力します。

6
1 22 333 4444 55555 666666
potato

505606561

9
123456 23456 3456 123456 23456 3456 123456 23456 3456
atoatoato

624732688