Problem Description

Unagi is enjoying a taiko game. In this game, you hit the taiko drum according to the string displayed on the screen. If the displayed string is $ S $, you hit the center of the drum, and if it is $ T $, you hit the edge of the drum. In this game, several strings are displayed in a row, and you can clear the game by hitting the drum in order according to these strings. However, the intervals between the displayed strings are too narrow, making it unclear where the strings are separated.

Unagi, who wants to clear the game, decided to count the number of correct ways to separate the displayed string. A correct way of separation is a method where each part of the separated string matches either string $ S $ or string $ T $.

Input Format

The input is given from the standard input in the following format:

$ X $ $ S $ $ T $

• The first line contains the string $X\ (1\ ≦\ |X|\ ≦\ 1000)$ displayed on the screen. Here, $ |X| $ represents the length of string $ X $.
• The second line contains the string $S\ (1\ ≦\ |S|\ ≦\ |X|)$ that instructs to hit the center of the drum.
• The third line contains the string $T\ (1\ ≦\ |T|\ ≦\ |X|,\ S\ \neq\ T)$ that instructs to hit the edge of the drum.
• All input strings are composed only of lowercase alphabets (a-z).
• It is guaranteed that there is at least one correct way to separate the displayed string.

Output Format

Output the number of correct ways to separate the displayed string modulo $1,000,000,007\ (10^9+7)$ in one line. Also, include a newline at the end of the output.

Sample Input and Output

Sample Input #1

dondonkatsudon
don
katsu

Sample Output #1

1

Sample Input #2

aaaaa
aaa
aa

Sample Output #2

2

Sample Input #3

ffffffffffffffffffffffffffffffffffffffffffffffffffffffff
f
ff

Sample Output #3

435293607

Notes/Hints

Sample Explanation 1

You can separate it as $ don,don,katsu,don $. There are no other correct ways to separate it.

Sample Explanation 2

There are two ways to separate it: as $ aaa,aa $ or as $ aa,aaa $.

Sample Explanation 3

The answer can be very large, so remember to find the remainder when divided by $ 1,000,000,007 $.

见题面 Input 部分

见题面 Output 部分