bzoj#P4214. 黄昏下的礼物

黄昏下的礼物

题目描述

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

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

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

输入格式

共两行。

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

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

输出格式

仅一行,即符合条件的字符串 SS 的个数,答案模 104+710^4+7

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

样例

hzw
2
4

样例说明

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

hzwzhwzhzwwhzhwhwzwh

数据规模与约定

对于 100%100\% 的数据:T200|T|\le 200N109N\le 10^9TT 中仅包含小写字母。