AT_ttpc2019_g Palindromic Love Letter

九头龙从一个女孩那里收到了一个只包含小写英文字母、长度为 $N$ 的回文串 $S$。 然而，九头龙的弟子爱酱对这个回文串进行了如下恶作剧： - 对 $S$ 的第 $i$ 个字符（$1 \leq i \leq N$）进行**恰好** $K$ 次操作，每次将其更改为不同的小写英文字母（同一个位置可以被多次选择）。 给定恶作剧后的字符串 $T$ 和整数 $K$，请你求出可能作为原始回文串的方案数，对 $10^9+7$ 取模。

输入通过标准输入按以下格式给出。 > $N$ $K$ $T$

输出可能作为原始回文串的方案数，对 $10^9+7$ 取模。

### 限制条件 - $1 \leq N \leq 2 \times 10^5$ - $0 \leq K \leq 10^9$ - $|T| = N$ - $T$ 仅由小写英文字母组成 ### 样例解释 1 - `aabaa`、`abbba` 满足条件。 ### 样例解释 2 - 注意必须**恰好**进行 $K$ 次操作。 由 ChatGPT 4.1 翻译