Counting Substrings

Limits 1s, 512 MB

You are given a string t, a prefix p, and a suffix s. You have to find the number of distinct substrings starting with the prefix p and ending with the suffix s.

Input

There are three lines of input consisting of string t, prefix p, and suffix s. All the strings are lowercase Latin letters.

$1 \leq |t|, |p|, |s| \leq 10^5$

Output

The only line of output is the number of distinct substrings starting with p and ending with s.

Samples

Input	Output
abcabc a bc	2
There are 3 substrings starting with a and ending with bc are abc, abc and abcabc. Among these abc and abcabc are distinct substring.

Input	Output
ababababa a b	4

Input	Output
abacbcdada a a	7