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

Помогите Марии посчитать количество способов и скоротать время.

Формат входных данных

В первой строке дана строка s (1 ⩽ |s| ⩽ 10⁶). Во второй строке дана строка t (1 ⩽ |t| ⩽ 10⁶). Строки состоят из строчных латинских букв.

Формат выходных данных

Выведите одно число - искомое количество способов выбрать подстроку 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