CF494B.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__a__i__s__a__i + 1... s__b__i (string s is considered as 1-indexed).

As the number of ways can be rather large print it modulo 109 + 7.

哈梅德最近发现了一个字符串 $t$，并突然对其产生了浓厚的兴趣。他花了好几天时间试图在自己拥有的其他字符串中找出所有 $t$ 的出现位置。最终，他感到疲惫不堪，开始思考如下问题：给定一个字符串 $s$，有多少种方式从中提取 $k\geq 1$ 个互不重叠的子串，使得每个子串都包含字符串 $t$ 作为其子串？更准确地说，你需要计算满足以下条件的两个序列 $a_1, a_2, \dots, a_k$ 和 $b_1, b_2, \dots, b_k$ 的方案数：

• $k \geq 1$
• 
• 
• 
• 字符串 $t$ 是子串 $s_{a_i}s_{a_i+1}\dots s_{b_i}$ 的子串（字符串 $s$ 视为从 $1$ 开始编号）。

由于方案数可能非常大，请将结果对 $10^9 + 7$ 取模后输出。

Input consists of two lines containing strings s and t (1 ≤ |s|, |t| ≤ 105). Each string consists of lowercase Latin letters.

输入包含两行，分别表示字符串 $s$ 和 $t$（$1 \le |s|, |t| \le 10^5$）。每个字符串均由小写拉丁字母组成。

Print the answer in a single line.

在一行中输出答案。