Time Limit : sec, Memory Limit : KB
English / Japanese  

Repeated Spell

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.

Input

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

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.

Sample Input 1

abab
ab

Sample Output 1

3

Sample Input 2

aaaabaaaabaaaabaaaab
aaaaa

Sample Output 2

4368

Sample Input 3

data
structure

Sample Output 3

0