配点 : 100 点
問題文
九头龙小姐是一个名字仅由小写英文字母组成的女孩。 N 回文 我收到了 S 。
然而,九头龙的弟子爱酱对这个回文数做了以下恶作剧。 将第
- S 可以得到第 i \ (1 \leq i \leq N) 个字符更改为不同的小写字母。 只是
执行 K 次
(但是,假设可以多次选择同一位置的字符。)
被恶作剧后的字符串 给定 T 和整数 可以获得第 K ,计算有多少个可能的原始回文。 10^9 + 7 后求余数。
制約
- N 是 您也可以写 1 \leq N \leq 2 \times 10^{5} 的整数 选择
- K 是 您也可以写 0 \leq K \leq 10^{9} 的整数 选择
- |T| = N
- T 仅由小写字母组成
入力
输入是按以下格式从标准输入给出的。
N K T
出力
找出可能的原始回文数。 打印除以 10^9 + 7 后的余数。
入力例 1
5 1 abbaa
出力例 1
2
aabaa,abbba满足条件。
入力例 2
4 1 aaaa
出力例 2
0
- 执行操作即可 请注意,它已完成 K 次。
入力例 3
1 100 a
出力例 3
26
入力例 4
11 7 abracadabra
出力例 4
1019576