404764: GYM101628 A Arthur's Language

Arthur is an extremely important person and rarely has the time to talk. To minimize the time spent with words, he developed his own language, which he uses on a daily basis. However, it's very hard to understand whatever comes out of his mouth.

In order to improve his interaction with the rest of the world, Arthur has asked the Narratives Industrial Complex (CIN in Portuguese) to develop a program which receives a speech S produced by Arthur and a pattern w and prints how many distinct ways we can obtain w by only removing characters from S. Two ways are considered distinct if there is an index 0 ≤ i < |S| such as S_i is present in one and not in the other.

Since you are considered the most experienced programmer in CIN, your team has trusted you the task of writing this program.

The first line consists of a string S(1 ≤ |S| ≤ 10⁵), representing Arthur's speech. S contains only lower and upper case letters.

The second and last line consists of a string w(1 ≤ |w| ≤ 10), the pattern to be searched.

Print a single integer: The number of distinct ways to obtain w by removing letters from S. Because this number can be large, print the remained of this number divided by 1000000007 = 10⁹ + 7

weewrshkim
sim

1

qqqaaabbbcccfffrrr
qabcfr

729