問題一覧 > 通常問題

No.1845 Long Substrings

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 87
作問者 : 👑 potato167 / テスター : tatyam nok0
お気に入りにしたユーザー ProblemId : 6904 / 自分の提出
問題文最終更新日: 2022-01-17 15:40:07
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 332 (順位表) の他の問題:

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.

That is, the string $T$ has length $\sum_{i=1}^{N}A_i$, and the following holds for every $i$:

  • The $(1+\sum_{k=1}^{i-1}A_k)$-th through $(\sum_{k=1}^{i}A_k)$-th characters are the same as the $i$-th character of $S$.

Find the number of distinct strings that can occur as a non-empty subsequence of the string $T$. Since the answer can be very large, output it modulo $(10^9+7)$.

▼What is a subsequence? A string obtained from a given string by removing 0 or more of its characters and arranging the remaining characters in their original order.

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
  • For $1 \leq i\leq N-1$, $S_i\neq S_{i+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
8

$T={}$aabb, and the possible non-empty subsequences of $T$ are the $8$ strings a, aa, aab, aabb, ab, abb, b, bb, so output $8$.

Sample 2
Input
3
1 1 1
ioi
Output
6

$T={}$ioi, and the possible non-empty subsequences of $T$ are the $6$ strings i, ii, io, ioi, o, oi, so output $6$.

Sample 3
Input
1
27
k
Output
27
Sample 4
Input
6
1 22 333 4444 55555 666666
potato
Output
606835344

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。