← 返回题目列表

Codeforces · 506/E

E. 北裕太先生的礼物

中文机器翻译题面 查看原题

Kitayuta先生好心给了你一个由小写英文字母组成的字符串s。要求您在 s 中插入恰好 n 个小写英文字母,使其成为回文。 (回文是向前和向后读取相同的字符串。例如,“noon”、“testset”和“a”都是回文,而“test”和“kitayuta”则不是。)您可以选择任意 n 个小写英文字母,并将它们中的每一个插入到 s 的任何位置,可能是到 s 的开头或结尾。即使可以通过插入少于 n 个字母将 s 变成回文,您也必须恰好插入 n 个字母。

求这样可以得到的回文数,模10007。

输入

第一行包含字符串 s (1 ≤ |s| ≤ 200)。 s中的每个字符都是一个小写英文字母。

第二行包含一个整数 n (1 ≤ n ≤ 109)。

输出

打印可获得的回文数,模 10007。

示例

输入 #1

revive
1

输出 #1

1

输入 #2

add
2

输出 #2

28

注意

对于第一个样本,您可以通过在“revive”末尾插入“r”来获取回文“reviver”。

对于第二个样本,可以获得以下28个回文:“adada”、“adbda”、...、“adzda”、“dadad”和“ddadd”。