Petr#

2000ms

262144K

Description:

Long ago, when Petya was a schoolboy, he was very much interested in the Petr# language grammar. During one lesson Petya got interested in the following question: how many different continuous substrings starting with the s_begin and ending with the s_end (it is possible s_begin = s_end), the given string t has. Substrings are different if and only if their contents aren't equal, their positions of occurence don't matter. Petya wasn't quite good at math, that's why he couldn't count this number. Help him!

Input:

The input file consists of three lines. The first line contains string t. The second and the third lines contain the s_begin and s_end identificators, correspondingly. All three lines are non-empty strings consisting of lowercase Latin letters. The length of each string doesn't exceed 2000 characters.

Output:

Output the only number — the amount of different substrings of t that start with s_begin and end with s_end.

Sample Input:

round
ro
ou

Sample Output:

Sample Input:

codeforces
code
forca

Sample Output:

Sample Input:

abababab
a
b

Sample Output:

Sample Input:

aba
ab
ba

Sample Output:

Note:

In the third sample there are four appropriate different substrings. They are: ab, abab, ababab, abababab.

In the fourth sample identificators intersect.

Informação

Provedor Codeforces

Código CF113B