题目描述

给定两个字符串 $S_1$ 和 $S_2$，均由小写字母组成。
求 $S_1$ 中有多少个子序列恰好等于 $S_2$。
答案可能很大，请对 $10^9+7$ 取模。

子序列的定义：从原串中删除零个或多个字符后得到的字符串，要求剩下的字符相对顺序保持不变。例如 "abc" 是 "aebdc" 的一个子序列。

输入格式

共两行，每行一个字符串。
第一行：字符串 $S_1$
第二行：字符串 $S_2$

输出格式

一行一个整数，表示 $S_1$ 中等于 $S_2$ 的子序列个数对 $10^9+7$ 取模的结果。

样例

abcabc
abc

4

样例 1 解释
四个子序列分别取位置 $(1,2,3)$、$(1,2,6)$、$(1,5,6)$、$(4,5,6)$。

rabbbit
rabbit

3

样例 2 解释
三个子序列分别是移除第一个 b、第二个 b 或第三个 b。

aaaaa
aa

10

样例 3 解释
从 $5$ 个 a 中任选 $2$ 个组成子序列，共 $\binom{5}{2}=10$ 种。

数据范围与提示

• 对于 $30\%$ 的数据：$|S_1| \le 1000$，$|S_2| \le 10$。
• 对于 $100\%$ 的数据：$1 \le |S_1| \le 10^5$，$1 \le |S_2| \le 10$，且 $|S_2| \le |S_1|$。
• 字符串仅包含小写字母。
• 建议使用 long long 存储中间结果，并记得对 $10^9+7$ 取模。