题目描述

给定一个小写字符串 $s$ 和一个正整数 $n$。

要求在 $s$ 中插入恰好 $n$ 个小写字符使其回文的方案数，两个方案不同当且仅当它们得到的串不同，与插入顺序和位置无关。

$|s| \le 200$，$n \le 10^9$，答案对 $10^4 + 7$ 取模。

输入格式

第一行一个字符串 $s$。

第二行一个整数 $n$。

输出格式

一个整数表示答案，对 $10^4 + 7$ 取模。

revive
1

1

add
2

28