Профессор Далл очень любит придумывать новые "хорошие" хеш-функции для строк. Недавно он опубликовал статью с описанием следующего метода. Любимая строка W считается одним из параметров алгоритма. Другим параметром является не превосходящее длины строки W натуральное число K. Хеш-функция считается для строки S. Сначала в строке S находятся все такие ее подстроки, которые являются анаграммами строки W. Из всех этих анаграмм выбираются наибольшая в смысле лексикографического порядка строка A_1 и наименьшая - A_2. Далее для каждой пары подстрок длины K из A_1 и A_2 считается количество одинаковых символов в одинаковых позициях. Все эти величины складываются - это и есть искомое значение. Если в S нет подстрок, являющихся анаграммами W, значение хеш-функции считается равным 0.
Подстрокой называется любая последовательность идущих подряд символов данной строки. Анаграмма - строка, получающаяся перестановкой букв данной строки.
В первой строке входного файла записано натуральное число K. Во второй строке записана строка W. Ее длина - натуральное число, не превосходящее 3000. Число K не превосходит длины строки W. В третьей строке входного файла содержится строка S. Ее длина - натуральное число, не превосходящее 100000. Гарантируется, что количество позиций строки S, в которых начинаются подстроки, являющиеся анаграммами W, не превосходит 2000. Все строки состоят только из строчных латинских букв.
Выведите искомое значение хеш-функции Далла.
Пояснение к примеру 1: Подстроки-анаграммы - bab, abb, bba (в порядке появления). Наибольшая - bba, наименьшая - abb. В каждой строке всего 2 подстроки длины K = 2. Количество совпадений у bb и ab - 1, у bb и bb -2, у ba и ab - 0, у ba и bb - 1. Всего 4 совпадения.