AlgoUniversity
  • Go Back
Discussion
Substring And Subsequence :

Author

Ayush Gangwani

Difficulty Level : Hard

Submissions : 219

Asked In : Uber

Marks :20

: 4 | : 2

Given two non-empty strings $$$s$$$ and $$$t$$$, consisting of lowercase Latin letters. Your task is to calculate the number of different pairs of $$$\textbf{(a b)}$$$ such that $$$a$$$ is a substring of string $$$s$$$, $$$b$$$ is a subsequence of string $$$t$$$, and the content of $$$a$$$ and $$$b$$$ is the same. Two pairs are considered different, if they contain different substrings of string $$$s$$$ or different subsequences of string $$$t$$$.

A substring of $$$s$$$ is a non-empty string $$$x = s[a... b] = s_as_{a + 1}... s_b (1 \le a \le b \le |s|)$$$. Two substrings $$$s[a... b]$$$ and $$$s[c... d]$$$ are considered to be different if $$$a ≠ c$$$ or $$$b ≠ d.$$$

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 \le p_1 \lt p_2 \lt ... \lt p_{|y|} \le |s|)$$$. 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 \le |s| \le 1000)$$$, and the second one contains $$$t$$$ $$$(1 \le |t| \le 1000)$$$. Both strings consist of lowercase Latin letters.

Output

Print a single number — the number of different pairs of $$$\textbf{(a b)}$$$ such that $$$a$$$ is a substring of string $$$s$$$, $$$b$$$ is a subsequence of string $$$t$$$, and the content of $$$a$$$ and $$$b$$$ is the same. As the answer can be rather large, print it modulo $$$1000000007 (10^9 + 7)$$$.

Example

Input
aa
aa
Output
5 

Note

In the sample testcase, following are the valid $$$\textbf{(a b)}$$$ pairs:

  • $$$s[1...1] \hspace{8pt} t[1]$$$
  • $$$s[2...2] \hspace{8pt} t[1]$$$
  • $$$s[1...1] \hspace{8pt} t[2]$$$
  • $$$s[2...2] \hspace{8pt} t[2]$$$
  • $$$s[1...2] \hspace{8pt} t[1 \hspace{3pt} 2]$$$

You need to login to view your submissions.

You need to login to view all submissions.

Loading...

Result : Executed

Loading...

Feel something is wrong with the test cases?

Result : Accepted

Test Cases :

You need to Log In
We're glad that you want to attempt this problem!

But to Run or Submit the Problem, you need to Log In.

Continue to Log In
Challenge Submitted!

Your challenge has been submitted successfully.

You will get a response soon via WhatsApp or Email.

Challenge
Facing issue while trying to solve the problem! Don't worry, we got you covered!

Do let us know your issue.

Looks good!
Please enter your issue / feedback.

How do we get in touch with you?
Looks good!
Please enter your phone no.
Looks good!
Please enter your email address.