Hamed 最近发现了一根弦 t 并突然变得非常喜欢它。他花了几天时间试图在他拥有的其他字符串中找到 t 的所有出现位置。最后他累了,开始思考下面的问题。给定一个字符串 s,有多少种方法可以从中提取 k ≥ 1 个不重叠的子串,使得每个子串都包含字符串 t 作为子串?更正式地说,您需要计算选择满足以下要求的两个序列 a1, a2, ..., ak 和 b1, b2, ..., bk 的方法数:
- k ≥ 1
- $$$$
- $$\forall i \left( 1 \leq i \leq k \right) b_i \geq a_i$$
- $$\forall i \left( 2 \leq i \leq k \right) a_i > b_{i-1}$$
- $$\forall i \left( 1 \leq i \leq k \right)$$ t 是字符串 saisai + 1... sbi 的子字符串(字符串 s 被视为 1 索引)。
由于方式的数量可以相当大,所以打印它模 109 + 7。
输入
输入由两行组成,其中包含字符串 s 和 t (1 ≤ |s|, |t| ≤ 105)。每个字符串均由小写拉丁字母组成。
输出
在一行中打印答案。
示例
输入 #1
ababa aba
输出 #1
5
输入 #2
welcometoroundtwohundredandeightytwo d
输出 #2
274201
输入 #3
ddd d
输出 #3
12