bzoj#P4214. 黄昏下的礼物
黄昏下的礼物
题目描述
另一个世界里,每个孤寂的黄昏,Nagisa 总是拿着她的礼盒,在那曾经樱花飞散的坡道旁的湖边等待。终于,Tomoya 带着 Ushi 向她微笑着走来,停在她身边,接过她手中的礼盒,缓缓拆开——里面满满装着这个世界中,每个伙伴的思念。透过金光,在湖面上映着那一端小镇的模样。看着美丽的小镇,看着人们的笑脸,看着那些思念的话语,故友的问候,Nagisa 与 Tomoya 相拥在一起,十指紧扣,享受这难得的温馨时刻。而这黄昏下珍贵的礼物,在年幼的 Ushi 看来,不过是堆看起来很好玩的字符。
回家后的 Ushi 躺在 Nagisa 怀里回想着刚才的画面,她想知道那些字符所组成的话都是些什么意思,可她已经记不起那么多了。现在她只记得,那些都是小写英文字母,且那些字符组成了一个回文串 ,同时她还记得一些字符以及它们的相对位置,这些字符按相对位置组成了字符串 ,剩下的 个字符及所有字符的具体位置她都忘记了。现在 Ushi 想知道有多少种可能的字符串能符合她的记忆,让她好去问 Nagisa。
由于 Ushi 还年幼,只认识小于 的非负整数,所以你只需告诉她模 后的结果。
输入格式
共两行。
第一行一个字符串 ,表示 Ushi 还记得的字符及它们的相对位置。
第二行一个非负整数 ,表示还有 个字符 Ushi 不记得了。
输出格式
仅一行,即符合条件的字符串 的个数,答案模 。
具体的意思可以通过样例来加深理解。
样例
hzw
2
4
样例说明
对于第一个样例的四个可能字符串 :
hzwzh
,wzhzw
,whzhw
,hwzwh
。
数据规模与约定
对于 的数据:,, 中仅包含小写字母。