Известно, что палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Например, палиндромами являются строки «A», «ABA», «ABBA», а строки «AB», «AAB», «ABAB» палиндромами не являются.
Рассмотрим некоторую строку S, состоящую только из латинских букв A и B. Назовем запрещенными все строки длины n, которые состоят также только из букв A и B и содержат S в качестве подстроки. Например, если S = «AB» и n =3, то существует четыре запрещенных строки— «AAB», «ABA», «ABB» и «BAB». Остальные строки будет называть допустимыми.
Требуется написать программу, которая для заданной строки S длиной не более пяти символов и заданного числа n определяет количество допустимых строк длины n, которые являются палиндромами.
Формат входных данных
Первая строка входного файла содержит строку S. Длина строки S не превосходит пяти. Вторая строка содержит число n (1 ≤ n ≤ 100).
Формат выходных данных
Выведите в выходной файл одно число — количество строк длины n, которые являются палиндромами и не содержат S в качестве подстроки.
Примеры входного и выходного файлов
| входные данные |
выходные данные |
AB
3 |
2 |
Пояснение к примеру
В приведенном примере две искомые строки — «AAA» и «BBB».