CF163A Substring and Subsequence

有一天，Polycarpus 得到了两个非空字符串 $s$ 和 $t$，它们均由小写拉丁字母组成。Polycarpus 很擅长字符串处理，于是他立刻想知道，有多少对不同的“$x$$y$”对，其中 $x$ 是字符串 $s$ 的一个子串，$y$ 是字符串 $t$ 的一个子序列，并且 $x$ 和 $y$ 的内容完全相同。如果一对中的 $s$ 的子串不同或 $t$ 的子序列不同，则认为这两个对是不同的。请阅读完整题目以理解不同子串和子序列的定义。 字符串 $s$ 的长度是其字符个数，记作 $|s|$。我们可以将 $s$ 写作 $s = s_{1}s_{2}...\,s_{|s|}$。 $s$ 的子串是指形如 $x = s[a...\,b] = s_{a} s_{a+1}...\,s_{b}$ 的非空字符串（$1 \leq a \leq b \leq |s|$）。例如，“code”和“force”都是“codeforces”的子串，而“coders”不是。当且仅当 $a \neq c$ 或 $b \neq d$ 时，两个子串 $s[a...\,b]$ 和 $s[c...\,d]$ 被认为是不同的。例如，若 $s = $“codeforces”，则 $s[2...2]$ 和 $s[6...6]$ 是不同的，即使它们的内容相同。 $s$ 的子序列是指形如 $y = s[p_{1} p_{2}...\,p_{|y|}] = s_{p_1} s_{p_2}...\,s_{p_{|y|}}$ 的非空字符串（$1 \leq p_{1} < p_{2} < ... < p_{|y|} \leq |s|$）。例如，“coders”是“codeforces”的子序列。如果 $u=s[p_{1} p_{2}...\,p_{|u|}]$，$v=s[q_{1} q_{2}...\,q_{|v|}]$，当 $p$ 序列与 $q$ 序列不同，则认为这两个子序列不同。

输入共两行。第一行为字符串 $s$（$1 \leq |s| \leq 5000$），第二行为字符串 $t$（$1 \leq |t| \leq 5000$）。两个字符串均由小写拉丁字母组成。

输出一个整数——满足要求的不同“$x$$y$”对的数量，即 $x$ 是 $s$ 的子串、$y$ 是 $t$ 的子序列，且 $x$ 与 $y$ 的内容相同的对数。由于答案可能很大，输出对 $1000000007$ 取模后的结果。

我们来列出第一个样例中所有包含在答案里的“$x$$y$”对：“$s[1...1]$ $t[1]$”，“$s[2...2]$ $t[1]$”，“$s[1...1]$ $t[2]$”，“$s[2...2]$ $t[2]$”，“$s[1...2]$ $t[1\,2]$”。 由 ChatGPT 5 翻译