5811: 【系列题】子序列(九)不同的子序列

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:22 Solved:4

Description

给你两个字符串 s t ,统计并返回在 s子序列t 出现的个数,结果需要对 109 + 7 取模。

Input

两行字符串

第一行为字符串s

第二行为字符串t

Output

一个整数 ,即s子序列t 出现的个数对109 + 7 取模的结果。

Sample Input Copy

rabbbit
rabbit

Sample Output Copy

3

HINT

样例说明:

输入:s = "rabbbit", t = "rabbit"

输出3

解释: 如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案

rabbbit

rabbbit

rabbbit


数据范围:

1 <= s.length, t.length <= 1000
st 由英文字母组成