说明

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10⁹ + 7 取模。

输入格式

两行字符串

第一行为字符串s

第二行为字符串t

输出格式

一个整数 ，即s 的 子序列 中 t 出现的个数对10⁹ + 7 取模的结果。

样例

rabbbit
rabbit

3

提示

样例说明：

输入：s = "rabbbit", t = "rabbit"


输出：3

解释： 如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。

rabbbit

rabbbit

rabbbit

数据范围：

1 <= s.length, t.length <= 1000
s 和 t 由英文字母组成