黄昏下的礼物

时间限制:40s      空间限制:768MB

题目描述

另一个世界里,每个孤寂的黄昏,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


题目来源

没有写明来源