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