题目描述

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

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

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

输入格式

共两行。

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

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

输出格式

仅一行，即符合条件的字符串 $S$ 的个数，答案模 $10^4+7$。

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

样例

hzw
2

4

样例说明

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

hzwzh，wzhzw，whzhw，hwzwh。

数据规模与约定

对于 $100\%$ 的数据：$|T|\le 200$，$N\le 10^9$，$T$ 中仅包含小写字母。