3918: CF163 - A. Substring and Subsequence
[Creator : ]
Description
One day Polycarpus got hold of two non-empty stringssandt, consisting of lowercase Latin letters. Polycarpus is quite good with strings, so he immediately wondered, how many different pairs of "x y" are there, such that $x$ is a substring of strings, $y$ is a subsequence of stringt, and the content of $x$ and $y$ is the same. Two pairs are considered different, if they contain different substrings of string $s$ or different subsequences of string $t$. Read the whole statement to understand the definition of different substrings and subsequences.
The length of string $s$ is the number of characters in it. If we denote the length of the string $s$ as $|s|$, we can write the string as $s=s_1s_2...s_{|s|}$.
Asubstringofsis a non-empty string $x=s[a...b]=s_as_{a+1}...s_b\ (1≤a≤b≤|s|)$. For example, "code" and "force" are substrings or "codeforces", while "coders" is not. Two substrings $s[a...b]$ and $s[c...d]$ are considered to be different if $a≠c$ or $b≠d$. For example, if s="codeforces",s[2...2] and s[6...6] are different, though their content is the same.
A subsequence of $s$ is a non-empty string $y=s[p_1p_2...p_{|y|}]=s_{p_1}s_{p_2}...s_{p_{|y|}}\ (1≤p_1<p_2<...<p_{|y|}≤|s|)$. For example, "coders" is a subsequence of "codeforces". Two subsequences $u=s[p_1p_2...p_{|u|}]$ and $v=s[q_1q_2...q_{|v|}]$ are considered different if the sequences $p$ and $q$ are different.
Asubstringofsis a non-empty string $x=s[a...b]=s_as_{a+1}...s_b\ (1≤a≤b≤|s|)$. For example, "code" and "force" are substrings or "codeforces", while "coders" is not. Two substrings $s[a...b]$ and $s[c...d]$ are considered to be different if $a≠c$ or $b≠d$. For example, if s="codeforces",s[2...2] and s[6...6] are different, though their content is the same.
A subsequence of $s$ is a non-empty string $y=s[p_1p_2...p_{|y|}]=s_{p_1}s_{p_2}...s_{p_{|y|}}\ (1≤p_1<p_2<...<p_{|y|}≤|s|)$. For example, "coders" is a subsequence of "codeforces". Two subsequences $u=s[p_1p_2...p_{|u|}]$ and $v=s[q_1q_2...q_{|v|}]$ are considered different if the sequences $p$ and $q$ are different.
Input
The input consists of two lines.
The first of them contains $s\ (1≤|s|≤5,000)$.
The second one contains $t\ (1≤|t|≤5,000)$.
Both strings consist of lowercase Latin letters.
The first of them contains $s\ (1≤|s|≤5,000)$.
The second one contains $t\ (1≤|t|≤5,000)$.
Both strings consist of lowercase Latin letters.
Output
Print a single number − the number of different pairs "x y" such that x is a substring of string s, y is a subsequence of string t, and the content of x and y is the same. As the answer can be rather large, print it modulo $10^9+7$.
Sample 1 Input
aa
aa
Sample 1 Output
5
Let's write down all pairs "x y" that form the answer in this sample: "s[1...1] t[1]", "s[2...2] t[1]", "s[1...1] t[2]","s[2...2] t[2]", "s[1...2] t[12]".
Sample 2 Input
codeforces
forceofcode
Sample 2 Output
60