测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A6961. 潜藏的指令

编程题 普及/提高-

题目描述

特工小明截获了一段极长的加密信号字符串 $S$。情报部门告诉他,这段信号中隐藏着一个核心指令 $T$。

核心指令 $T$ 是通过“伪装”的方式隐藏在 $S$ 中的。具体来说,指令 $T$ 的字符按顺序分散在 $S$ 的各个位置(不需要连续,但必须保持前后相对顺序)。

例如:信号 $S = \text{"babgbag"}$,指令 $T = \text{"bag"}$。
我们可以找到 5 种不同的方式从 $S$ 中提取出 $T$(下标从 0 开始):
1. $S[0], S[1], S[3]$ ("**ba**b**g**bag") -> "bag"
2. $S[0], S[1], S[6]$ ("**ba**bgba**g**") -> "bag"
3. $S[0], S[5], S[6]$ ("**b**abgb**ag**") -> "bag"
4. $S[2], S[5], S[6]$ ("ba**b**gb**ag**") -> "bag"
5. $S[4], S[5], S[6]$ ("babg**bag**") -> "bag"

为了评估情报的可靠性,小明需要计算出:**在信号 $S$ 中,总共有多少种不同的方式可以组成指令 $T$?**

**由于方案数可能非常巨大,请输出方案数对 $10^9 + 7$ 取模后的结果。**

输入格式

输入共两行。
第一行包含一个字符串 $S$(表示加密信号)。
第二行包含一个字符串 $T$(表示核心指令)。

输出格式

输出一个整数,表示 $T$ 在 $S$ 中作为子序列出现的次数对 $1000000007$ 取模后的结果。

输入输出样例

输入 #1
rabbbit
rabbit
输出 #1
3
输入 #2
babgbag
bag
输出 #2
5

说明/提示

### 数据范围

- 对于 $100\%$ 的数据:
- $S$ 和 $T$ 仅由英文字母组成。
- $1 \le |T| \le |S| \le 1000$。
- 答案需对 $10^9 + 7$ 取模。
上一题 去做题 下一题