Description

另一个世界里，每个孤寂的黄昏，Nagisa总是拿着她的礼盒，在那曾经樱花飞散的坡道旁的湖边等待。终于，Tomoya带着Ushi向她微笑着走来，停在她身边，接过她手中的礼盒，缓缓拆开——里面满满装着这个世界中，每个伙伴的思念。透过金光，在湖面上映着那一端小镇的模样。看着美丽的小镇，看着人们的笑脸，看着那些思念的话语，故友的问候，Nagisa与Tomoya相拥在一起，十指紧扣，享受这难得的温馨时刻。而这黄昏下珍贵的礼物，在年幼的Ushi看来，不过是堆看起来很好玩的字符。

回家后的Ushi躺在Nagisa怀里回想着刚才的画面，她想知道那些字符所组成的话都是些什么意思，可她已经记不起那么多了。现在她只记得，那些都是小写英文字母，且那些字符组成了一个回文串S，同时她还记得一些字符以及它们的相对位置，这些字符按相对位置组成了字符串T，剩下的n个字符及所有字符的具体位置她都忘记了。现在Ushi想知道有多少种可能的字符串能符合她的记忆，让她好去问Nagisa。

由于Ushi还年幼，只认识小于10007的非负整数，所以你只需告诉她模10007后的结果。

Format

Input

共两行。

第一行一个字符串T，表示Ushi还记得的字符及它们的相对位置。

第二行一个非负整数n，表示还有n个字符Ushi不记得了。

Output

仅一行，即符合条件的字符串S的个数，答案模10007.

具体的意思可以通过样例来加深理解。

Samples

hzw
2

4

Limitation

对于第一个样例的四个可能字符串S：

“hzwzh”，”wzhzw”，“whzhw”，“hwzwh”

|T|<=200,N<=10^9