Когда Петя еще учился в школе, он очень увлекался грамматикой языка Petr#. На одном из уроков Петю заинтересовал следующий вопрос: сколько различных подстрок, начинающихся строкой sbegin этого языка и заканчивающихся строкой send (возможно, sbegin = send), существует у заданной строки t. Подстроки называются различными, если различно их содержание, при этом позиции вхождения не имеют значения. В школе Петя не дружил с математикой, поэтому он не смог посчитать это количество. Помогите ему!
Выходные данные
Выведите единственное число — количество различных подстрок строки t, которые начинаются со строки sbegin и заканчиваются строкой send.
Примечание
В третьем тесте есть четыре различные подходящие подстроки: ab, abab, ababab, abababab.
В четвертом тесте подстроки, соответствующие sbegin и send, пересекаются.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
round
ro
ou
|
1
|
|
2
|
codeforces
code
forca
|
0
|
|
3
|
abababab
a
b
|
4
|
|
4
|
aba
ab
ba
|
1
|