Obsessive String

题意翻译

【题目描述】 Hamed最近发现了一个字符串T,然后突然就很喜爱这个字符串。他花了一些时间试图找出所有包含T为子串的其他字符串。最后,他变得很累,然后开始考虑下面的问题。 给你一个字符串S,问你有多少种方式提取长度不为0的不重叠的子串,每个子串都必须包含字符串T。 更正式地说,你需要计算选择两个序列A和B,满足以下要求 k>=1 ![](https://cdn.luogu.org/upload/vjudge_pic/CF494B/bb2a9663e220d590c509be53cd8da3ca9ca602e8.png) ![](https://cdn.luogu.org/upload/vjudge_pic/CF494B/15cb6228063cc47cd8627d4598e4f8fe6e9779d4.png) ![](https://cdn.luogu.org/upload/vjudge_pic/CF494B/bb2a9663e220d590c509be53cd8da3ca9ca602e8.png) ![](https://cdn.luogu.org/upload/vjudge_pic/CF494B/24d9cacc311eaf7cd7460855212493822ca3c22b.png) 因为输出数字太大,所以要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 $ - ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF494B/c5deac271ac89767b4839ccdea2b77dd1eb1d964.png) - ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF494B/15cb6228063cc47cd8627d4598e4f8fe6e9779d4.png) - ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF494B/bb2a9663e220d590c509be53cd8da3ca9ca602e8.png) - ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF494B/24d9cacc311eaf7cd7460855212493822ca3c22b.png) $ 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