Sunny is fond of words. He got a new game to play with his cousin Sonali. He gives her a long string and two other smaller strings (A and B). Now he asks Sonali to find the number of all the subsequences of the long string that are greater than equal to smaller string A and less than equal to smaller string B.

Help Sonali to find the answer.

Note: Comparison of two strings is regarded same as that done by the string:compare function.

Empty string is not regarded as a subsequence.

Input

Each input consists of 3 lines. First line has the TEXT string.

2nd and 3rd line contain two smaller strings A and B.

Output

One number which gives the count such that A ≤ subsequence of (TEXT) ≤ B.

Constraints

Input will consist of all lowercase characters.

1 ≤ Length of TEXT ≤ 25

1≤ Length of A and B ≤ Length of TEXT

Example

Input:
coforc
co
fc

Output:
24