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”。