Підрядок паліндрома#11524
Якийсь щедрий чоловік люб'язно надав вам рядок , що складається з малих літер латинського алфавіту. Він просить вас вставити рівно малих літер латинського алфавіту в так, щоб утворився паліндром. Паліндром — це рядок, який читається однаково зліва направо і справа наліво. Наприклад, "noon", "testset" і "a" є паліндромами, тоді як "test" і "codeforces" — ні.
Ви можете вибрати будь-які малих літер латинського алфавіту і вставити кожну з них у будь-яку позицію в , включаючи початок або кінець. Необхідно вставити рівно літер, навіть якщо можна перетворити на паліндром, вставивши менше літер.
Знайдіть кількість паліндромів, які можна отримати таким чином, за модулем .
У першому рядку подано рядок s~(1 \le |s| \le 200). Кожен символ у — це мала літера латинського алфавіту.
У другому рядку записано ціле число n~(1 \le n \le 10^9).
Виведіть кількість паліндромів, які можна отримати, за модулем .
У першому прикладі можна отримати паліндром "reviver", вставивши 'r' в кінець "revive".
У другому прикладі можна отримати наступні паліндромів: "adada", "adbda", ..., "adzda", "dadad" і "ddadd".
Приклад 1
Приклад 2