28714번 - Оно 다국어

Очень голодный Пеннивайз вновь проснулся спустя 27 лет. Преследуя детей, он случайно отвлекся, и им удалось спрятаться в комнате с кодовым замком. На двери комнаты имеется табло с двумя строками $s$ и $t$.

Чтобы узнать код, клоун должен посчитать количество способов выбрать непустую подстроку $s$, которую можно собрать из букв строки $t$. Подстрокой строки называется отрезок подряд идущих символов. Две подстроки считаются различными, если различаются позиции их начала или конца.

Помогите Пеннивайзу получить код и позавтракать!

В первой строке дана строка $s$ ($1 \le |s| \le 10^6$). Во второй строке дана строка $t$ ($1 \le |t| \le 10^6$).

Строки состоят из строчных латинских букв.

Выведите одно число --- искомое количество способов выбрать подстроку $s$.

В первом тесте существуют следующие способы выбрать подстроку (выделена скобками):

1. [a]aa
2. a[a]a
3. aa[a]
4. [aa]a
5. a[aa]

Во втором тесте существуют следующие способы выбрать подстроку:

1. [a]bacaba
2. a[b]acaba
3. ab[a]caba
4. aba[c]aba
5. abac[a]ba
6. abaca[b]a
7. abacab[a]
8. [ab]acaba
9. a[ba]caba
10. ab[ac]aba
11. aba[ca]ba
12. abac[ab]a
13. abaca[ba]
14. a[bac]aba
15. aba[cab]a