Мистер Китаюта любезно предоставил Вам строку s из строчных букв латинского алфавита. Он просит вас вставить ровно n строчных букв латинского алфавита в s так, чтобы получился палиндром. Палиндром — это строка, которая читается одинаково в обоих направлениях. Например, «noon», «testset» и «a» — палиндромы, а «test» и «kitayuta» — нет.
Вы можете выбрать любые n строчных букв латинского алфавита и вставить каждую из них в любую позицию s, в частности, можно вставить в начало или в конец s. Надо вставить ровно n букв, даже если данную строку можно сделать палиндромом, вставив менее n букв.
Найдите количество палиндромов, которые можно получить таким способом, по модулю 10007.
Выходные данные
Выведите количество палиндромов, которые можно получить, по модулю 10007.
Примечание
В первом примере можно получить палиндром «reviver», вставив «r» в конец «revive».
Во втором примере можно получить следующие 28 палиндромов: «adada», «adbda», ..., «adzda», «dadad» and «ddadd».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
revive
1
|
1
|
|
2
|
add
2
|
28
|