题目描述

给定两个字符串 $s$ 和 $t$。定义一种合法的截取方案为，在字符串 $s$ 中截取若干（大于 $0$）个互不相交的子串，满足 $t$ 是每个这些子串的子串。

请你输出总方案数模 $10^9 + 7$ 的值。

输入格式

输入共两行。第一行一个字符串 $s$，第二行一个字符串 $t$。

保证 $1 \leq |s|, |t| \leq 10^5$，字符串中只包含小写拉丁字母。

输出格式

输出共一行，一个非负整数表示答案。

ababa
aba

5

welcometoroundtwohundredandeightytwo
d

274201

ddd
d

12