8214: BZOJ4214：黄昏下的礼物

另一个世界里，每个孤寂的黄昏，Nagisa总是拿着她的礼盒，在那曾经樱花飞散的坡道旁的湖边等待。终于，Tomoya带着Ushi向她微笑着走来，停在她身边，接过她手中的礼盒，缓缓拆开——里面满满装着这个世界中，每个伙伴的思念。透过金光，在湖面上映着那一端小镇的模样。看着美丽的小镇，看着人们的笑脸，看着那些思念的话语，故友的问候，Nagisa与Tomoya相拥在一起，十指紧扣，享受这难得的温馨时刻。而这黄昏下珍贵的礼物，在年幼的Ushi看来，不过是堆看起来很好玩的字符。 回家后的Ushi躺在Nagisa怀里回想着刚才的画面，她想知道那些字符所组成的话都是些什么意思，可她已经记不起那么多了。现在她只记得，那些都是小写英文字母，且那些字符组成了一个回文串S，同时她还记得一些字符以及它们的相对位置，这些字符按相对位置组成了字符串T，剩下的n个字符及所有字符的具体位置她都忘记了。现在Ushi想知道有多少种可能的字符串能符合她的记忆，让她好去问Nagisa。 由于Ushi还年幼，只认识小于10007的非负整数，所以你只需告诉她模10007后的结果。

输入格式

共两行。 第一行一个字符串T，表示Ushi还记得的字符及它们的相对位置。 第二行一个非负整数n，表示还有n个字符Ushi不记得了。

输出格式

仅一行，即符合条件的字符串S的个数，答案模10007. 具体的意思可以通过样例来加深理解。

样例输入

hzw
2

样例输出

4

提示

对于第一个样例的四个可能字符串S： “hzwzh”，”wzhzw”，“whzhw”，“hwzwh” |T|<=200,N<=10^9

题目来源

没有写明来源