Prefix and Suffix

Count the distinct substrings of S that both start with string A and end with string B, where A and B may overlap within a substring.

Medium6StringHash mapString matchingNo attempts yetTime limit2sMemory limit512 MB

Description

Examples3

Problem

You are given three strings $S$ , $A$ , and $B$ .

Write a program that counts how many distinct substrings of $S$ start with $A$ and end with $B$ . A substring is a contiguous block of $S$ , and two substrings made of the same characters count as one even when they appear at different positions. Inside one substring, the block taken by $A$ and the block taken by $B$ may overlap.

Input

The first line contains $S$ , the second line contains $A$ , and the third line contains $B$ . All three strings consist of lowercase letters only, and each length is between 1 and 2,000.

Output

Print the number of distinct substrings of $S$ that start with $A$ and end with $B$ .

Hint

If $S$ is abababab, $A$ is a, and $B$ is b, the substrings that satisfy the condition are ab, abab, ababab, and abababab, so there are four of them.