A9713 | Obsessive String

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.