Obsessive String

### 题目描述 给定两个字符串 $s$ 和 $t$。定义一种合法的截取方案为，在字符串 $s$ 中截取若干（大于 $0$）个互不相交的子串，满足 $t$ 是每个这些子串的子串。 请你输出总方案数模 $10^9 + 7$ 的值。 ### 输入格式 输入共两行。第一行一个字符串 $s$，第二行一个字符串 $t$。 ### 输出格式 输出共一行，一个非负整数表示答案。 ### 数据范围 保证 $1 \leq |s|, |t| \leq 10^5$，字符串中只包含小写拉丁字母。

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.

ababa
aba

5

welcometoroundtwohundredandeightytwo
d

274201

ddd
d

12