A promo engine hides a target keyword inside a longer source string. Count the number of distinct ways to choose positions from the source string s so that the chosen characters, in order, spell exactly the target t. Two ways are different if the set of chosen positions differs, even if the resulting characters are identical. Because the count can be large, output it modulo 1000000007.
Line 1: the source string s.
Line 2: the target string t.
A single integer: the number of distinct subsequences of s equal to t, modulo 1000000007.
s <= 200t <= 200Example 1
Input
rabbbit rabbit
Expected
3
Explanation
rabbit is formed by keeping r, a, two of the three b's, i, t; there are 3 ways to pick which two b's, so the answer is 3.
Example 2
Input
babgbag bag
Expected
5
Explanation
There are 5 distinct position sets in babgbag that spell bag.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →