Підрядок паліндрома

Якийсь щедрий чоловік люб'язно надав вам рядок $s$, що складається з малих літер латинського алфавіту. Він просить вас вставити рівно $n$ малих літер латинського алфавіту в $s$ так, щоб утворився паліндром. Паліндром — це рядок, який читається однаково зліва направо і справа наліво. Наприклад, "noon", "testset" і "a" є паліндромами, тоді як "test" і "codeforces" — ні.

Ви можете вибрати будь-які $n$ малих літер латинського алфавіту і вставити кожну з них у будь-яку позицію в $s$, включаючи початок або кінець. Необхідно вставити рівно $n$ літер, навіть якщо $s$ можна перетворити на паліндром, вставивши менше $n$ літер.

Знайдіть кількість паліндромів, які можна отримати таким чином, за модулем $10007$.

Вхідні дані

У першому рядку подано рядок $s(1\le |s|\le 200)$. Кожен символ у $s$ — це мала літера латинського алфавіту.

У другому рядку записано ціле число $n(1\le n\le 10^9)$.

Вихідні дані

Виведіть кількість паліндромів, які можна отримати, за модулем $10007$.

Приклади

У першому прикладі можна отримати паліндром "reviver", вставивши 'r' в кінець "revive".

У другому прикладі можна отримати наступні $28$ паліндромів: "adada", "adbda", ..., "adzda", "dadad" і "ddadd".