题目名称

E. Mr. Kitayuta's Gift

题目描述

给定一个仅由小写英文字母组成的字符串 s。你需要恰好向 s 中插入 n 个小写字母（插入位置可在任意位置，也可以在开头或结尾），得到一个回文串。

• 回文串：从左到右读与从右到左读完全相同，例如 "noon", "testset", "a" 是回文串，而 "test", "kitayuta" 不是。
• 你可以自由选择插入的字母是什么，以及每个字母插入到哪里。
• 即使用少于 n 个字符就能变成回文，也必须插入正好 n 个字符。

求：通过上述方式可以得到的不同回文串的数量，对 10007 取模。

输入格式

• 第一行：字符串 s（1 ≤ |s| ≤ 200），只包含小写英文字母。
• 第二行：整数 n（1 ≤ n ≤ 10^9）。

输出格式

输出一个整数：答案对 10007 取模后的结果。

样例 1

输入：

revive
1

输出：

1

说明：插入 'r' 到末尾得到 "reviver"。

样例 2

输入：

add
2

输出：

28

说明：可得到 28 个不同回文串（如 "adada", "adbda", …, "adzda", "dadad", "ddadd" 等）。

部分分