Задача 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