Задача F. Перестановки с подстрокой

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Даны строки S и P, состоящие из малых латинских букв. Требуется определить сколько различных слов, составленных из букв строки S, содержат в себе подстроку P.

Например, если S = dcba, P = bc, то получится 11 строк: bc, abc, bca, dbc, bcd, adbc, dabc, abcd, dbca, bcad, bcda.

Формат входного файла

Первая строка содержит строку S, вторая — строку P.

Формат выходного файла

В выходном файле должно содержаться единственное число — количество слов.

Ограничения

Длины строк находятся в диапазоне от 1 до 12 букв. Все буквы строки S различны.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
dbca
bc
11
2
xyz
xx
0

0.036s 0.010s 15