# 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 \$ - ![](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
``````