113_B. Petr#
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 sbegin and ending with the send (it is possible sbegin = send), 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 sbegin and send 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 sbegin and end with send.

Examples

Input

round
ro
ou


Output

1


Input

codeforces
code
forca


Output

0


Input

abababab
a
b


Output

4


Input

aba
ab
ba


Output

1

Note

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

In the fourth sample identificators intersect.
```python
from functools import cmp_to_key


def calc_lcp(s, sa):
    rank = [0 for _ in range(len(s))]
    for i in range(len(s)):
        rank[sa[i]] = i
    lcp = [0 for _ in range(len(s) - 1)]
    h = 0
    for i in range(len(s)):
        if rank[i] < len(s) - 1:
            while max(i, sa[rank[i] + 1]) + h < len(s) and s[i + h] == s[sa[rank[i] + 1] + h]:
                h += 1
            lcp[rank[i]] = h
            if h > 0:
                h -= 1
    return lcp, rank

def suffix_array(s):
    sa = [i for i in range(len(s))]
    rank = [ord(s[i]) for i in range(len(s))]
    k = 1
    while k < len(s):
        key = [0 for _ in range(len(s))]
        base = max(rank) + 2
        for i in range(len(s)):
            key[i] = rank[i] * base + (rank[i + k] + 1 if i + k < len(s) else 0)
        sa.sort(key=(lambda i: key[i]))

        rank[sa[0]] = 0
        for i in range(1, len(s)):
            rank[sa[i]] = rank[sa[i - 1]] if key[sa[i - 1]] == key[sa[i]] else i
        k *= 2
    # for i in sa:
    #     print(s[i:])
    return sa

def kmp(s, p):
    pi = [0 for _ in range(len(p))]
    k = 0
    for i in range(1, len(p)):
        while k > 0 and p[k] != p[i]:
            k = pi[k - 1]
        if p[k] == p[i]:
            k += 1
        pi[i] = k

    k = 0
    resp = []
    for i in range(len(s)):
        while k > 0 and p[k] != s[i]:
            k = pi[k - 1]
        if p[k] == s[i]:
            k += 1
        if k == len(p):
            resp.append(i - len(p) + 1)
            k = pi[k - 1]
    return resp

def lower_bound(list, value):
    left = 0
    right = len(list)
    while left < right:
        mid = int((left + right) / 2)
        if list[mid] < value:
            left = mid + 1
        else:
            right = mid
    return left


s = input()
start = input()
end = input()

indStart = kmp(s, start)
indEnd = kmp(s, end)

if len(indStart) == 0 or len(indEnd) == 0:
    print(0)

else:
    sa = suffix_array(s)
    lcp, rank = calc_lcp(s, sa)

    ind = rank[indStart[0]]
    for st in indStart:
        ind = min(ind, rank[st])

    resp = len(indEnd) - lower_bound(indEnd, sa[ind] + max(0, len(start) - len(end)))
    while ind < len(lcp) and lcp[ind] >= len(start):
        ind += 1
        resp += len(indEnd) - lower_bound(indEnd, sa[ind] + max(0, max(lcp[ind - 1] + 1, len(start)) - len(end)))

    print(resp)


```