No.1848 Long Prefixes
Problem Statement
You are given an integer $N$, an integer sequence $A$ of length $N$, and a string $S$ of length $N$ consisting of lowercase English letters.
The string $T$ is obtained by starting from the empty string and, in the order $i=1,2,...,N$, appending the $i$-th character of $S$ to the end $A_{i}$ times.
In other words, the string $T$ has length $\sum_{i=1}^{N}A_i$, and the following holds for every $i$.
- The characters from the $(1+\sum_{k=1}^{i-1}A_k)$-th to the $(\sum_{k=1}^{i}A_k)$-th are the same as the $i$-th character of $S$.
Here, for the string $T$, let $T_i$ be the string consisting of the $i$-th and subsequent characters of $T$, and let $f(i)$ be the number of characters that match between $T$ and $T_i$ when compared from the beginning (the length of their longest common prefix).
Find $\sum_{i=1}^{|T|}f(i)$ modulo $(10^{9}+7)$.
Constraints
- $1\leq N \leq 2\times 10^5$
- $1\leq A_{i} \leq 10^{9}\ (1\leq i \leq N)$
- $N$ and all elements of $A$ are integers
- $S$ is a string of length $N$ consisting only of lowercase English letters
- $S_i\neq S_{i+1}$ for $1 \leq i\leq N-1$
Input
$N$ $ A_1 \; A_2 \; ...\;A_N$ $S$
Output
Output the answer modulo $(10^{9}+7)$. Print a newline at the end.
Sample
Sample 1
Input
2 2 2 ab
Output
5
$T={}$aabb, and
since $T_{1}={}$aabb, $T_{2}={}$abb, $T_{3}={}$bb, $T_{4}={}$b, the answer is $4+1+0+0=5$.
Sample 2
Input
1 27 k
Output
378
Sample 3
Input
6 1 22 333 4444 55555 666666 tomato
Output
782598
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
tatyam