Obsessive String

题意翻译

【题目描述】 Hamed最近发现了一个字符串T，然后突然就很喜爱这个字符串。他花了一些时间试图找出所有包含T为子串的其他字符串。最后，他变得很累，然后开始考虑下面的问题。 给你一个字符串S，问你有多少种方式提取长度不为0的不重叠的子串，每个子串都必须包含字符串T。 更正式地说，你需要计算选择两个序列A和B，满足以下要求 k>=1     因为输出数字太大，所以要mod 10^9+7 。 【输入】 输入总共两行 第一行输入一个字符串S 第二行输入一个字符串T 【输出】 输出一个数字，代表可行的方案数。

题目描述

Hamed has recently found a string $ t $ and suddenly became quite fond of it. He spent several days trying to find all occurrences of $ t $ in other strings he had. Finally he became tired and started thinking about the following problem. Given a string $ s $ how many ways are there to extract $ k>=1 $ non-overlapping substrings from it such that each of them contains string $ t $ as a substring? More formally, you need to calculate the number of ways to choose two sequences $ a_{1},a_{2},...,a_{k} $ and $ b_{1},b_{2},...,b_{k} $ satisfying the following requirements: - $ k>=1 $ -  -  -  -  $ t $ is a substring of string $ s_{ai}s_{ai}+1... s_{bi} $ (string $ s $ is considered as $ 1 $ -indexed). As the number of ways can be rather large print it modulo $ 10^{9}+7 $ .

输入输出格式

输入格式

Input consists of two lines containing strings $ s $ and $ t $ ( $ 1<=|s|,|t|<=10^{5} $ ). Each string consists of lowercase Latin letters.

输出格式

Print the answer in a single line.

输入输出样例

输入样例 #1

ababa
aba

输出样例 #1

5

输入样例 #2

welcometoroundtwohundredandeightytwo
d

输出样例 #2

274201

输入样例 #3

ddd
d

输出样例 #3

12