← 返回题目列表

Codeforces · 163/A

A. 子串和子序列

中文机器翻译题面 查看原题

有一天,Polycarpus 得到了两个非空字符串 s 和 t,由小写拉丁字母组成。 Polycarpus对字符串很在行,所以他立即想知道,有多少对不同的“x y”,使得x是字符串s的子串,y是字符串t的子序列,并且x和y的内容是相同的。如果两个对包含字符串 s 的不同子串或字符串 t 的不同子序列,则认为它们是不同的。阅读整个语句以了解不同子字符串和子序列的定义。

字符串 s 的长度是其中的字符数。如果我们将字符串 s 的长度表示为 |s|,则可以将字符串写为 s = s1s2... s|s|。

s 的子字符串是非空字符串 x = s[a... b] = sasa + 1... sb (1 ≤ a ≤ b ≤ |s|)。例如,“code”和“force”是子字符串或“codeforces”,而“coders”则不是。如果 a ≠ c 或 b ≠ d,则两个子串 s[a... b] 和 s[c... d] 被认为是不同的。例如,如果 s="codeforces",则 s[2...2] 和 s[6...6] 不同,尽管它们的内容相同。

s 的子序列是非空字符串 y = s[p1p2... p|y|] = sp1sp2... sp|y| (1 ≤ p1 < p2 < ... < p|y| ≤ |s|)。例如,“coders”是“codeforces”的子序列。如果序列 p 和 q 不同,则两个子序列 u = s[p1p2... p|u|] 和 v = s[q1q2... q|v|] 被认为是不同的。

输入

输入由两行组成。其中第一个包含 s (1 ≤ |s| ≤ 5000),第二个包含 t (1 ≤ |t| ≤ 5000)。两个字符串均由小写拉丁字母组成。

输出

打印单个数字 — 不同对“x y”的数量,其中 x 是字符串 s 的子字符串,y 是字符串 t 的子序列,并且 x 和 y 的内容相同。由于答案可能相当大,因此打印它对 1000000007 (109 + 7) 取模。

示例

输入 #1

aa
aa

输出 #1

5

输入 #2

codeforces
forceofcode

输出 #2

60

注意

让我们写下第一个示例中形成答案的所有对“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]”。