← 返回题目列表

Codeforces · 494/B

B. 痴迷的字符串

中文机器翻译题面 查看原题

Hamed 最近发现了一根弦 t 并突然变得非常喜欢它。他花了几天时间试图在他拥有的其他字符串中找到 t 的所有出现位置。最后他累了,开始思考下面的问题。给定一个字符串 s,有多少种方法可以从中提取 k ≥ 1 个不重叠的子串,使得每个子串都包含字符串 t 作为子串?更正式地说,您需要计算选择满足以下要求的两个序列 a1, a2, ..., ak 和 b1, b2, ..., bk 的方法数:

- k ≥ 1
- $$$$
- $$\forall i \left( 1 \leq i \leq k \right) b_i \geq a_i$$
- $$\forall i \left( 2 \leq i \leq k \right) a_i > b_{i-1}$$
- $$\forall i \left( 1 \leq i \leq k \right)$$  t 是字符串 saisai + 1... sbi 的子字符串(字符串 s 被视为 1 索引)。

由于方式的数量可以相当大,所以打印它模 109 + 7。

输入

输入由两行组成,其中包含字符串 s 和 t (1 ≤ |s|, |t| ≤ 105)。每个字符串均由小写拉丁字母组成。

输出

在一行中打印答案。

示例

输入 #1

ababa
aba

输出 #1

5

输入 #2

welcometoroundtwohundredandeightytwo
d

输出 #2

274201

输入 #3

ddd
d

输出 #3

12