After discovering and investigating the ancient nation of Iwashiro, our researchers finally found a temple in the center of Iwashiro. The temple housed a stone tablet dedicated to the god of Iwashiro. On the tablet, there are two strings of text, one sentence and one spell.
In Iashiro, The number of times a spell appears in a sentence has an important meaning. However, even if the spell appears sporadically in the sentence, it is considered to appear once. For example, if the sentence is "abab" and the spell is "ab", then "ab" appears three times in "abab", including non-consecutive occurrences (three patterns: abab, abab, abab.)
Given a sentence and a spell, make a program to output the number of times the spell appears in the sentence.
The input is given in the following format.
t b
In the first line, the string t represents the text written on the tablet is given. In the second line, the string b represents the spell written on the tablet is given. Both strings are made up of only lowercase letters and are between 1 and 1000 characters long.
Output the number of times the spell appears in a sentence in a line. However, the value can be very large, so output the remainder divided by 1,000,000,007 instead.
abab ab
3
aaaabaaaabaaaabaaaab aaaaa
4368
data structure
0