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.
Input format
Line 1: the source string s.
Line 2: the target string t.
Output format
A single integer: the number of distinct subsequences of s equal to t, modulo 1000000007.
Constraints
- 1 <= length of
s<= 200 - 1 <= length of
t<= 200 - Both strings consist of lowercase English letters only.