题目描述

给定两个字符串 $S$ 与 $T$，请计算，它们有多少公共的子序列？

所谓子序列，是指从原序列中选择部分或全部元素组成的新序列。选出的元素在原序列中不必连续，但要保持在原序列中的顺序。

只要下标不同，哪怕数字相等，也算成不同的子序列。

注意这道题目中空串不算子序列。

由于答案很大，只要输出答案模 $1,000,000,007$ 的余数。

输入格式

• 第一行：一个字符串 $S$
• 第二行：一个字符串 $T$

输出格式

ab
ba

2

aba 
baa

8

样例解释 2

aa有四种组合，b有一种组合，ba有两种组合，aa有一种组合

数据范围

设 $|S|$ 表示 $S$ 的长度，$|T|$ 表示 $T$ 的长度

• $30\%$ 的数据，$1\leq |S|, |T|\leq 10$
• $60\%$ 的数据，$1\leq |S|, |T|\leq 200$
• $100\%$ 的数据，$1\leq |S|, |T|\leq 3000$
• 保证 $S$ 与 $T$ 只包含英文字母。

来源

改编自 ABC130E Common Subsequence