E. Подарок мистера Китаюта
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
768 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мистер Китаюта любезно предоставил Вам строку s из строчных букв латинского алфавита. Он просит вас вставить ровно n строчных букв латинского алфавита в s так, чтобы получился палиндром. Палиндром — это строка, которая читается одинаково в обоих направлениях. Например, «noon», «testset» и «a» — палиндромы, а «test» и «kitayuta» — нет.

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

Найдите количество палиндромов, которые можно получить таким способом, по модулю 10007.

Входные данные

В первой строке следует строка s (1 ≤ |s| ≤ 200). Каждый символ в s — это строчная буква латинского алфавита.

Во второй строке записано целое число n (1 ≤ n ≤ 109).

Выходные данные

Выведите количество палиндромов, которые можно получить, по модулю 10007.

Примеры
Входные данные
revive
1
Выходные данные
1
Входные данные
add
2
Выходные данные
28
Примечание

В первом примере можно получить палиндром «reviver», вставив «r» в конец «revive».

Во втором примере можно получить следующие 28 палиндромов: «adada», «adbda», ..., «adzda», «dadad» and «ddadd».