Counting Embeddings

Difficulty: 1800 3000 ms 128 MB

strings dp

Count how many distinct ways T occurs in S as a subsequence (positions distinguish occurrences), modulo 10⁹+7.

Input: two lines: the text S, then the target T.

Output: the number of subsequence embeddings of T in S, mod 10⁹+7.

Constraints:

• 1 ≤ |S| ≤ 1000
• 1 ≤ |T| ≤ 100
• lowercase letters

Sample Tests

rabbbit
rabbit

3

abc
abc

1

Read the Editorial